POJ2686 Traveling by Stagecoach （状压DP）

将车票的使用情况用二进制表示状态，对其进行转移即可。

但是我一开始写的代码是错误的（注释部分），看似思路是正确的，但是暗藏很大的问题。

枚举S，我们要求解的是dp[S][v]，这个是从u转移过来的，不可以写成dp[S|(1<

 1 #include
 2 #include
 3 #include
 4 using namespace std;
 5 const double INF=0x3f3f3f3f;
 6 double ans;
 7 int n,m,p,a,b;
 8 int t[20];
 9 int dis[50][50];
10 double dp[1<<10][32];//dp[s][u]表示到达当前u点（使用s的车票）的最小花费 
11 
12 void solve(){
13     //memset(dp,0x3f,sizeof(dp));//整型数赋值,不可以
14     for(int i=0;i<(1<<(n+1));i++)
15         fill(dp[i],dp[i]+m+1,INF);
16     dp[0][a]=0;
17     ans=INF;
18     for(int S=0;S<(1<){
19         for(int u=1;u<=m;u++)
20             for(int i=0;i)
21                 if((S>>i)&1)//使用i车票
22                     for(int v=1;v<=m;v++)
23                         if(dis[u][v]>=0)
24                             dp[S][v]=min(dp[S][v],dp[S&~(1<double)t[i]);
25         ans=min(ans,dp[S][b]);                     
26     }
27 }
28 
29 /*void solve(){ //错误代码 
30     //memset(dp,0x3f,sizeof(dp));//整型数赋值,不可以
31     for(int i=0;i<(1<<(n+1));i++)
32         fill(dp[i],dp[i]+m+1,INF);
33     dp[0][a]=0;
34     ans=INF;
35     for(int S=0;S<(1<36         for(int u=1;u<=m;u++)
37             for(int i=0;i38                 if(!(S>>i)&1)//未使用i车票
39                     for(int v=1;v<=m;v++)
40                         if(dis[u][v]>=0)
41                             dp[S|(1<42         ans=min(ans,dp[S][b]);                     
43     }
44 }*/
45 
46 int main(){
47     while(~scanf("%d%d%d%d%d",&n,&m,&p,&a,&b)){
48         if(n+m+p+a+b==0) break;
49         for(int i=0;i"%d",&t[i]);
50         memset(dis,-1,sizeof(dis));
51         for(int i=0;i){
52             int u,v,w;
53             scanf("%d%d%d",&u,&v,&w);
54             dis[u][v]=dis[v][u]=w;
55         }
56         solve();
57         if(ans==INF) printf("Impossible\n");
58         else printf("%.3f\n",ans);
59     }
60     return 0;
61 }