题意：
有n个城市，一个人选择一个城市开始，游历其它城市，但是他不能到一个城市超过两次。
问是否能游历完这些城市，以及最少的花费。
思路：
一直读错题意，觉得是二进制状压，囧。
不超过两次，那么就是3进制状态压缩，预先把3的进制预处理出来，之后按照二进制同样的处理方法就行了。
还要先把某个数的3进制表示的第几位为0，1，2给预处理出来。
转移方程：
dp[S+p3[k]][k] = min(dp[S+p3[k][k],dp[S][j] + mp[j][k])，S的第k位小于2才能转移。
代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 const int inf = 0x3f3f3f3f; 6 const int N = 11; 7 int dp[100000][N]; 8 int mp[N][N]; 9 int p3[N]; 10 int num[100000][N]; 11 int main() 12 { 13 int n,m; 14 p3[0] = 1; 15 for (int i = 1;i <= 10;i++) p3[i] = p3[i-1]*3; 16 for (int i = 0;i < p3[10];i++) 17 { 18 int tmp = i; 19 int cnt = 0; 20 while (tmp) 21 { 22 num[i][cnt++] = tmp % 3; 23 tmp /= 3; 24 } 25 } 26 while (scanf("%d%d",&n,&m)!=EOF) 27 { 28 memset(mp,inf,sizeof(mp)); 29 memset(dp,inf,sizeof(dp)); 30 for (int i = 0;i < m;i++) 31 { 32 int a,b,c; 33 scanf("%d%d%d",&a,&b,&c); 34 a--,b--; 35 mp[a][b] = mp[b][a] = min(mp[a][b],c); 36 } 37 for (int i = 0;i < n;i++) 38 { 39 dp[p3[i]][i] = 0; 40 } 41 for (int i = 0;i < p3[n];i++) 42 { 43 for (int j = 0;j < n;j++) 44 { 45 if (dp[i][j] < inf && num[i][j] != 0) 46 { 47 for (int k = 0;k < n;k++) 48 { 49 if (num[i][k] < 2 && mp[j][k] < inf) 50 { 51 //printf("gg"); 52 dp[i+p3[k]][k] = min(dp[i+p3[k]][k],dp[i][j] + mp[j][k]); 53 } 54 } 55 } 56 } 57 } 58 int ans = inf; 59 for (int i=0;i < p3[n];i++) 60 { 61 int cnt = 0; 62 for (int j = 0;j < n;j++) if (num[i][j]) cnt++; 63 if (cnt == n) 64 { 65 for (int j = 0;j < n;j++) ans = min(ans,dp[i][j]); 66 } 67 } 68 printf("%d ",ans == inf ? -1 : ans); 69 } 70 return 0; 71 }