hdu3001_三进制状压dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3001
题意：n个城市，每个城市最多去两次，起点任意，问需要的最少旅费是多少？
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cstdlib>
  6 #include <cmath>
  7 #include <set>
  8 #include <map>
  9 #include <queue>
 10 #include <vector>
 11 #define INF 0x3f3f3f3f
 12 using namespace std;
 13 
 14 const int N = 10, M = 60100;
 15 int dp[M][N];
 16 int num[11][11], ab[11];
 17 int n, m, f[M][N];
 18 void find()
 19 {
 20     ab[0] = 1;
 21     for(int i = 1; i <= 10; ++i)
 22         ab[i] = 3 * ab[i - 1];
 23     for(int i = 0; i < M; i++)
 24     {
 25         int te = i;
 26         for(int j = 0; j < N; j++)
 27         {
 28             f[i][j] = te % 3;
 29             te /= 3;
 30         }
 31     }
 32 }
 33 int rec()
 34 {
 35     int sum = ab[n];
 36     for(int i = 0; i < sum; ++i)
 37         for(int j = 0; j < n; ++j)
 38             dp[i][j] = INF;
 39     for(int i = 0; i < n; i++)
 40         dp[ab[i]][i] = 0;
 41     for(int i = 1; i < sum; ++i)
 42     {
 43         for(int j = 0; j < n; ++j)
 44         {
 45             if(dp[i][j] == INF)
 46                 continue;
 47             if(f[i][j] != 0)
 48             {
 49                 for(int k = 0; k < n; ++k)
 50                 {
 51                     if(f[i][k] == 2 || k == j || num[j][k] == INF)
 52                         continue;     
 53                     int next = i + ab[k];
 54                     dp[next][k] = min(dp[next][k], dp[i][j] + num[j][k]);
 55                 }
 56             }
 57         }
 58     }
 59     int res = INF, s1 = 1, first = 0;     
 60     for(int i = 0; i < n; ++i)   
 61     {
 62         first += s1;  
 63         s1 *= 3;          
 64     }
 65     for(int i = first; i < sum; ++i)
 66     {
 67         int ok = 1;
 68         for(int j = 0; j < n; j++)//判断是否有城市没去过
 69         {
 70             if(f[i][j] == 0)
 71             {
 72                 ok = 0;
 73                 break;
 74             }
 75         }
 76         if(ok)
 77             for(int k = 0; k < n; ++k)
 78                 res = min(dp[i][k], res);
 79     }
 80     return res;
 81 }
 82 int main()
 83 {
 84     int a, b, c;
 85     find();
 86     while(~scanf("%d %d", &n, &m))
 87     {
 88         for(int i = 0; i < n; ++i)
 89             for(int j = 0; j < n; ++j)
 90                 num[i][j] = INF;
 91         for(int i = 0; i < m; ++i)
 92         {
 93             scanf("%d %d %d", &a, &b, &c);//还要判断重边
 94             num[a - 1][b - 1] = num[b - 1][a - 1] = min(c, num[a - 1][b - 1]);
 95         }
 96         int res = rec();                        
 97         if(res == INF)
 98             printf("-1
");
 99         else
100             printf("%d
", res);
101     }
102     return 0;
103 }