大意：
一个人要送n份货，给出一个矩阵，表示任意两个点间的直接路径长度，求从起点0送完这n份货（到达指定的n个地点）再回到起点0的最短时间。
经过任意顶点的次数不限。
分析：既然是可以过多个点，那我们可以想到先用FD算法求出两两顶点的最短路，
dp[i][j]表示在状态i的条件下到点j的最短时间，显然如果i == (1 << (j - 1))，表示从只经过点j，这时候dp[i][j] = dis[0][j]，否则就是要经过别的点到达j
这里枚举当前状态下经过的除了j的其他点，注意一定是当前状态下，采用类似Floyd的思想
最后dp[(1 << n) - 1][i]表示经过了所有点到达i，只要枚举dp[(1 << n) - 1][i] + dis[i][0]的最小值即可
#include<stdio.h> #include<algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 11; int n; int dp[1<<maxn][maxn];///dp[i][j]表示在状态i的条件下到点j的最短时间 int mp[maxn][maxn];/// 图，邻接矩阵，初始时记录顶点之间的原始距离，后来记录顶点之间的最短距离 void FD( ) { for(int k=0 ; k<=n ; k++) for(int i=0 ; i<=n ; i++) for(int j=0 ; j<=n ; j++) if(mp[i][j]>mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j]; } int main( ) { while(scanf("%d",&n)!=EOF) { if(n==0) break; for(int i=0 ; i<=n ; i++) for(int j=0 ; j<=n ; j++) scanf("%d",&mp[i][j]); FD( ); for ( int i = 0; i <= (1 << n) - 1; i++ ) { /// 枚举 所有的状态/所有组合 for ( int j = 1; j <= n; j++ ) { if ( i == (1 << (j - 1)) ) /// 初始值 dp[i][j] = mp[0][j]; /// dp[i][j]：在状态i的条件下到点j的最短时间 else { dp[i][j] = INF; for ( int k = 1; k <= n; k++ )//( i & (1 << (k - 1)) )判断第k位是否位1,也就是判断是否可以进过k点 if ( ( k != j ) && ( i & (1 << (k - 1)) ) ) /// 当前状态下 dp[i][j] = min( dp[i][j], dp[i ^ (1 << (j - 1))][k] + mp[k][j] ); } } } int ans = dp[(1 << n) - 1][1] + mp[1][0]; for ( int i = 2; i <= n; i++ ) /// 找出最短的回路 ans = min( ans, dp[(1 << n) - 1][i] + mp[i][0] ); printf ( "%d ", ans ); } return 0; }