题意：
有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 #include2 #include 3 #include 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\n",ans == inf ? -1 : ans);69 }70 return 0;71 }