WIKIOI 2800送外卖题解和分析

【题目链接】：

http://www.wikioi.com/problem/2800/

【分析】：

首先计算任意两点之间的最短路径，在动态规划开始之前先对状态进行预处理。其中state[i][j]表示i个1所处的位置的状态信息：即二进制表示中第j位为1时的状态信息。初始化阶段将所有点到起点的距离值设置为初始值，并设定每一位代表一个点是否已被访问过：例如, 第k位为1则表示第k个点已访问。随后遍历所有已访问过的节点，在每一步都枚举当前到达过的节点以及可能转移到的新节点。具体来说, 对于每一个当前到达过的节点j和新选择的目标节点k, 如果满足以下条件: 节点j已被访问过, 而目标节点k尚未被访问过, 则可以进行状态转移操作: 将新的状态定义为state[i+1][l|(1<<(k-1))], 并记录该状态下到达目标节点k的最小距离值 min(f[state[i+1][l|(1<<(k-1))]][k], f[state[i][l]][j] + map[j][k]) 。最终结果即是在所有可能的状态中找到距离起点最近的那个终点, 即从 ( (1<<N)- ¹ 的最后一位到达各个终点时的最小距离中选择最小的一个即可得到最优解。

【代码】：

 #include<stdio.h>

    
 #i