hdu 3001 Travelling

http://acm.hdu.edu.cn/showproblem.php?pid=3001
状压dp，一开始题意看错了，以为是每个点只能经过一次，题意是每个点经过不能超过2次。状态用三进制表示。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 11
 5 using namespace std;
 6 const int inf=1<<29;
 7 
 8 int n,m;
 9 int dp[100000][maxn];
10 int g[maxn][maxn];
11 int c[12];
12 int a[12];
13 
14 int ArrayToInt(int a[])//转化为十进制
15 {
16     int y=0;
17     for(int i=n-1; i>=0; i--)
18     {
19         y*=3;
20         y+=a[i];
21     }
22     return y;
23 }
24 void ToArray(int x)//转化为三进制
25 {
26     for(int i=0; i<n; i++)
27     {
28         a[i]=x%3;
29         x/=3;
30     }
31 }
32 
33 int main()
34 {
35     c[0]=1;
36     for(int i=1; i<=11; i++) c[i]=3*c[i-1];
37     while(scanf("%d%d",&n,&m)!=EOF)
38     {
39         for(int i=0; i<n; i++)
40         {
41             for(int j=0; j<n; j++)
42             {
43                 if(i==j)g[i][j]=0;
44                 else g[i][j]=inf;
45             }
46         }
47         for(int i=1; i<=m; i++)
48         {
49             int u,v,c;
50             scanf("%d%d%d",&u,&v,&c);
51             g[u-1][v-1]=g[v-1][u-1]=min(g[u-1][v-1],c);//去重边
52         }
53         memset(dp,-1,sizeof(dp));
54         for(int i=0; i<n; i++)
55         {
56             dp[c[i]][i]=0;
57         }
58         int ans=inf;
59         for(int i=0; i<c[n]; i++)
60         {
61             for(int j=0; j<n; j++)
62             {
63                 ToArray(i);
64                 if(dp[i][j]<0) continue;
65                 bool flag=true;
66                 for(int x=0; x<n; x++)
67                 {
68                     if(a[x]==0)
69                     {
70                         flag=false;
71                         break;
72                     }
73                 }
74                 if(flag)
75                 {
76                     ans=min(ans,dp[i][j]);
77                     continue;
78                 }
79                 for(int k=0; k<n; k++)
80                 {
81                     if(j==k||g[j][k]==inf||g[j][k]==0) continue;
82                     if(a[k]<2)
83                     {
84                         a[k]++;
85                         int xx=ArrayToInt(a);
86                         if(dp[xx][k]==-1) dp[xx][k]=dp[i][j]+g[j][k];
87                         else dp[xx][k]=min(dp[xx][k],dp[i][j]+g[j][k]);
88                         a[k]--;
89                     }
90                 }
91             }
92         }
93         if(ans==inf) printf("-1
");
94         else printf("%d
",ans);
95     }
96     return 0;
97 }
View Code