| Description The Pizazz Pizzeria prides itself in delivering pizzas to its customers as fast as possible. Unfortunately, due to cutbacks, they can afford to hire only one driver to do the deliveries. He will wait for 1 or more (up to 10) orders to be processed before he starts any deliveries. Needless to say, he would like to take the shortest route in delivering these goodies and returning to the pizzeria, even if it means passing the same location(s) or the pizzeria more than once on the way. He has commissioned you to write a program to help him. Input Input will consist of multiple test cases. The first line will contain a single integer n indicating the number of orders to deliver, where 1 ≤ n ≤ 10. After this will be n + 1 lines each containing n + 1 integers indicating the times to travel between the pizzeria (numbered 0) and the n locations (numbers 1 to n). The jth value on the ith line indicates the time to go directly from location i to location j without visiting any other locations along the way. Note that there may be quicker ways to go from i to j via other locations, due to different speed limits, traffic lights, etc. Also, the time values may not be symmetric, i.e., the time to go directly from location i to j may not be the same as the time to go directly from location j toi. An input value of n = 0 will terminate input. Output For each test case, you should output a single number indicating the minimum time to deliver all of the pizzas and return to the pizzeria. Sample Input 3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0 0 Sample Output 8 |
题意：从0号点开始，访问每个点后回到0号点的最短路，每个点可以多次访问，0号点也可以经过多次。
先用Floyd计算出每两点之间最短路，并记录最短路所经过的点的压缩状态，然后类似旅行商问题的dp。
$dp[zt][j]$表示状态zt下，第一次到j且最后停留在j的最短路。由于两点最短路径可能经过其它点，从而影响到zt，所以不能像一般的旅行商问题那样循环到$dp[i][j]$再去求$dp[i][j]$，而应该在循环到$dp[i][j]$之前就把$dp[i][j]$求好。具体就是每次循环到$dp[i][j]$就去计算与$dp[i][j]$相关的其他$dp[i']dp[j']$。
说实话，一开始我很怀疑这个思路是不是正确的。下面对这个过程进行分析，试图通过分析体现算法的正确性：
比如循环到$dp[i][j]$，我们之前已经把$dp[i][j]$计算好了，如果它仍没有被计算好，说明这个状态不存在，直接跳过就好。
现在根据已经计算好的$dp[i][j]$，遍历状态i从未踏足的点k，获得从j到k的最短路d[j][k]，和这个最短路径经过点的压缩状态$p[j][k]$，更新$dp[i|p[j][k]][k]$，这样$dp[i|p[j][k]][k]$经过多次更新，就能够满足上文的dp的定义了。
可能因为有时候被错误思路搞得身心俱疲，所以很容易怀疑自己的思路是不是正确的，也可以换个角度，把目光转向$dp[i|p[j][k]][k]$，它的变化过程就是由所有不同的j点到k点且总状态状态是$i|p[j][k]$的最短路中的最小值，所以能够想到这个思路是对的。
这道题的思想还是很值得学习的。具体看代码。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int MAXN = 11; int n; int d[MAXN][MAXN]; int p[MAXN][MAXN]; int dp[1<<MAXN][MAXN]; int main() { while(scanf("%d",&n)!=EOF&&n){ n++; for(int i=0;i<n;i++) for(int j=0;j<n;j++) { scanf("%d",&d[i][j]); p[i][j] = (1<<i)|(1<<j); } for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) { if(d[i][k]+d[k][j]<d[i][j]){ d[i][j] = d[i][k] + d[k][j]; p[i][j] = p[i][k] | p[k][j]; } } memset(dp,-1,sizeof(dp)); for(int j=0;j<n;j++) dp[p[0][j]][j] = d[0][j]; for(int i=1;i<(1<<n);i++) for(int j=0;j<n;j++) { if(dp[i][j]==-1) continue; for(int k=0;k<n;k++) { if(((1<<k)&i)==0) { if(dp[i|p[j][k]][k]==-1||dp[i|p[j][k]][k]>dp[i][j]+d[j][k]) dp[i|p[j][k]][k] = dp[i][j]+d[j][k]; } } } int ans=1000000000,zt=(1<<n)-1; for(int j=0;j<n;j++) { if(dp[zt][j]!=-1) ans = min(ans, dp[zt][j]+d[j][0]); } printf("%d ",ans); } }