题目链接 >http://poj.org/problem?id=3311<
题意：从0出发，经过所有点（点可以重复走）后回到0点，问最短路
思路分析：
这题和普通的最短路不太一样，因为题目要求每个点都要走一遍。
因此我们选择状压。
用SPFA直接开始做，f[i][status]表示到达点i时，状态为status时的最短路，答案就是f[0][(1<<(n+1))-1]
更新也和SPFA一模一样
/*By QiXingzhi*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define r read() #define Max(a,b) (((a)>(b)) ? (a) : (b)) #define Min(a,b) (((a)<(b)) ? (a) : (b)) using namespace std; typedef long long ll; const int N = 20; const int INF = 1061109567; inline int read(){ int x = 0; int w = 1; register int c = getchar(); while(c ^ '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c >= '0' && c <= '9') x = (x << 3) +(x << 1) + c - '0', c = getchar(); return x * w; } struct Pizza{ int u, sta; }; int n; int G[N][N],d[N][32768]; queue <Pizza> q; inline void Debug(int status){ int tmp[30]; memset(tmp,0,sizeof(tmp)); int tot = 0; while(status > 0){ tmp[++tot] = status % 2; status /= 2; } for(int i = tot; i > 0; --i){ printf("%d",tmp[i]); } } inline void SPFA(){ // printf("u = %d status = ",u); Debug(status); printf(" d = %d ",d[u][status]); memset(d,0x3f,sizeof(d)); d[0][0] = 0; Pizza tmp; tmp.u = 0, tmp.sta = 0; q.push(tmp); int u,status; while(!q.empty()){ Pizza __t = q.front(); Pizza __next; u = __t.u; status = __t.sta; q.pop(); for(int i = 0; i <= n; ++i){ if(G[u][i] == 0) continue; if(d[u][status] + G[u][i] < d[i][status ^ (1 << (i))]){ d[i][status ^ (1 << (i))] = d[u][status] + G[u][i]; __next.u = i; __next.sta = status ^ (1 << (i)); q.push(__next); } } } } int main(){ // freopen(".in","r",stdin); // freopen("debug.txt","w",stdout); while(1){ n = r; if(n == 0) break; for(int i = 0; i <= n; ++i){ for(int j = 0; j <= n; ++j){ G[i][j] = r; } } SPFA(); printf("%d ", d[0][(1<<(n+1))-1]); } return 0; }