hdu3001 题意: 给n个城市以及m条路。要求每个城市至多经过2次，求经过全部城市所需要的时间总花费是多少。 思路： 状态压缩。三进制进行压缩处理。可以提前处理好每个状态下每一位的情况。注意好下表细节，n个城市的话，状态的为0到bas[n]数组，即0到3的n次方（前闭后开）。 代码：
#include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; int n,m; int a,b,c; int dis[20][20]; int bas[20]; int cur[59051][12]; int dp[59051][12]; bool has(int sta,int pos) { // for(int i=0;i<10;i++) // { // int now=sta%3; // sta/=3; // if(i==pos) // { // if(now==1||now==2) // return 1; // else // return 0; // // } // } if(cur[sta][pos]) { return 1; } else return 0; } bool no(int sta,int pos) { // for(int i=0;i<10;i++) // { // int now=sta%3; // sta/=3; // if(i==pos) // { // if(now==1||now==0) // return 1; // else // return 0; // // } // } if(cur[sta][pos]==0||cur[sta][pos]==1) { return 1; } else return 0; } int getne(int sta,int pos) { int tmp=0; for(int i=9;i>=0;i--) { tmp=tmp*3+(cur[sta][pos]+1); } return tmp; } int main() { bas[0]=1; for(int i=1;i<12;i++) { bas[i]=bas[i-1]*3; } memset(cur,0,sizeof cur); // printf("%d\n",bas[10]); for(int i=0;i<=bas[10];i++) { int t; t=i; int cnt=0; while(t) { cur[i][cnt]=t%3; t/=3; cnt++; } } // printf("bas[%d]=%d\n",10,bas[10]); while(scanf("%d%d",&n,&m)!=EOF) { memset(dis,0x3f,sizeof dis); for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); a--; b--; dis[a][b]=dis[b][a]=min(dis[a][b],c); } // for(int k=0;k<n;k++) // { // for(int i=0;i<n;i++) // { // for(int j=0;j<n;j++) // { // dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); // } // } // } memset(dp,0x3f3f3f3f,sizeof dp); int ans=0x3f3f3f3f; for(int i=0;i<n;i++) { dp[bas[i]][i]=0; } for(int i=0;i<bas[n];i++) { int fff=1; for(int j=0;j<n;j++) { if(cur[i][j]==0) fff=0; if(dp[i][j]==0x3f3f3f3f) continue; // if(has(i,j)) for(int k=0;k<n;k++) { if(cur[i][k]<=1&&j!=k) { int ne=i+bas[k]; if(dis[j][k]==0x3f3f3f3f||dp[i][j]==0x3f3f3f3f) continue; dp[ne][k]=min(dp[ne][k],dp[i][j]+dis[j][k]); } } } if(fff) for(int j=0;j<n;j++) ans=min(ans,dp[i][j]); } // for(int i=0;i<n;i++) // { // ans=min(dp[bas[10]-1][i],ans); // } if(ans>=0x3f3f3f3f) { puts("-1"); continue; } printf("%d\n",ans); } return 0; }