Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5295 Accepted Submission(s): 1718
题意：一个地图可以从任意一个地点出发，到达遍历所有的点，每个点最多可以被访问2次，问这样遍历所有的点的最小边权和是多少。
题解：观察这个题的数据范围是10，而且要求每个点有3个状态：未被访问，被访问1次，被访问2次。是一个类似于汉密顿的问题（汉密顿问题是每个点经过且只经过一次）
考虑用状态压缩dp来写，但是一般的状态压缩是用0,1表示访问和未访问两个状态，所以用一个二进制数来表示这个地图的某个状态。而这个题是一个点有三个状态，未被访问，被访问一次，被访问2次。所以自然的想到用一个三进制数来表示，集合的运算完全类比于二进制的情况。
参见http://www.cnblogs.com/shanyr/p/4827563.html 的spfa思路
代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 #define N 11 9 #define INF 0x7f7f7f7f//注意memset里的0x7f的值在int中是0x7f7f7f7f 10 11 int mp[N][N]; 12 bool vis[177777][N]; 13 int dp[177777][N]; 14 queue<pair<int,int> > q; 15 bool ch(int s, int n) 16 { 17 for(int i = 0; i < n; i++) { 18 if(s%3 == 0) return false; 19 s /= 3; 20 } 21 return true; 22 }//检验最后的这个状态中是否是每个点都访问过 23 int main() 24 { 25 int n , m ; 26 while(~scanf("%d%d",&n,&m)) 27 { 28 memset(vis,0,sizeof(vis)); 29 memset(dp,0x7f,sizeof(dp)); 30 memset(mp,0x7f,sizeof(mp)); 31 for(int i =0 ;i < n ;i++) 32 mp[i][i] = 0; 33 dp[0][0] = 0; 34 vis[0][0] = 1; 35 q.push(make_pair(0,0)); 36 for(int i = 0; i < n; i++){ 37 dp[(int)(pow(3, i))][i] = 0; 38 q.push(make_pair(pow(3, i), i)); 39 } 40 int u, v , d; 41 for(int i =0 ; i < m ; i++) 42 { 43 scanf("%d%d%d",&u,&v,&d); 44 u--,v--; 45 mp[u][v] = mp[v][u] = min(mp[u][v],d); 46 } 47 int tm = pow(3,n)-1; 48 while(!q.empty()) 49 { 50 int s = q.front().first; 51 int u = q.front().second; 52 q.pop(); 53 vis[s][u] = 0; 54 int cur = s, ss; 55 for(int i = 0 ;i < n ; i++) 56 { 57 int bt = cur % 3; 58 cur /= 3;//因为要考虑到没有用的数，及这个位置已经是2了就要在这个位置的下一位考虑了 59 if(bt < 2) { 60 ss = s + pow(3, i); 61 if(dp[ss][i]>dp[s][u]+mp[i][u]){ 62 dp[ss][i] = dp[s][u] + mp[i][u]; 63 if(vis[ss][i] == 0){ 64 vis[ss][i] = 1; 65 q.push(make_pair(ss,i)); 66 } 67 } 68 } 69 } 70 } 71 //for(int i = 0; i < pow(3, n); i++) 72 // for(int j = 0; j < n; j++) 73 // printf("%d %d : %d\n", i, j, dp[i][j]); 74 int ans = INF; 75 for(int s = 0; s <= tm; s++) 76 for(int i = 0 ;i < n ;i++) 77 if(ch(s, n)) ans = min(ans,dp[s][i]); 78 if(ans==INF) printf("-1\n"); 79 else printf("%d\n",ans); 80 } 81 return 0; 82 }
原文：http://www.cnblogs.com/shanyr/p/4842938.html