hdu_3001_Travelling(状压DP)

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3001

题意：给你N个点，M条边，每个点最多走两次，问走完N个点最短的路程为多少。

题解：注意这题有重边，因为最多走两次，所以要用3进制来压缩状态，处理一下就行

 1 #include<cstdio>
 2 #include<cmath>
 3 #define FFC(i,a,b) for(int i=a;i<=b;i++)
 4 
 5 int n,m,s,g[11][11],dp[60000][11],inf=1e9,cnt,x,y,z,now,end,ans,cur;
 6 
 7 int main(){
 8     while(~scanf("%d%d",&n,&m)){
 9         end=pow(3,n)-1,ans=inf;
10         FFC(i,0,n)FFC(j,i,n)g[j][i]=g[i][j]=inf;
11         FFC(i,1,m){scanf("%d%d%d",&x,&y,&z);if(g[x][y]>z)g[x][y]=g[y][x]=z;}
12         FFC(i,0,n)FFC(j,1,end)dp[j][i]=inf;
13         FFC(i,1,n)dp[(int)pow(3,i-1)][i]=0;
14         FFC(i,0,end){
15             FFC(kk,1,n){
16             cur=i;FFC(k,1,kk-1)cur/=3;
17             if(cur%3==0)continue;
18             if(dp[i][kk]!=inf)FFC(j,1,n){
19                     now=1,cur=i;FFC(k,1,j-1)now*=3,cur/=3;
20                     if(cur%3<2&&kk!=j&&g[kk][j]!=inf){
21                         if(dp[i+now][j]>dp[i][kk]+g[kk][j])
22                             dp[i+now][j]=dp[i][kk]+g[kk][j];
23                     }
24                 }
25             }
26             cur=i,cnt=0;
27             while(cur){if(cur%3)cnt++;cur/=3;}
28             if(cnt==n)FFC(k,1,n)ans=ans>dp[i][k]?dp[i][k]:ans;
29         }
30         printf("%d
",ans==inf?-1:ans);
31     }
32     return 0;
33 }

View Code