Travelling

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7394    Accepted Submission(s): 2405 Problem Description After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He has decided to visit n cities(he insists on seeing all the cities!And he does not mind which city being his start station because superman can bring him to any city at first but only once.), and of course there are m roads here,following a fee as usual.But Mr Acmer gets bored so easily that he doesn't want to visit a city more than twice!And he is so mean that he wants to minimize the total fee!He is lazy you see.So he turns to you for help.   Input There are several test cases,the first line is two intergers n(1<=n<=10) and m,which means he needs to visit n cities and there are m roads he can choose,then m lines follow,each line will include three intergers a,b and c(1<=a,b<=n),means there is a road between a and b and the cost is of course c.Input to the End Of File.   Output Output the minimum fee that he should pay,or -1 if he can't find such a route.   Sample Input 2 1 1 2 100 3 2 1 2 40 2 3 50 3 3 1 2 3 1 3 4 2 3 10   Sample Output 100 90 7   Source 2009 Multi-University Training Contest 11 - Host by HRBEU   Recommend gaojie   提示

题意：

一个人需要在n个城市间找出起点且一个城市至多可以经过两次，求出必须经过所有城市的最小花费。如果无解则输出"-1"。

思路：

n很小可以利用三进制来存下每个城市经过次数的状态。dp数组第一维就是状态，第二维目前该人所在城市的编号，具体细节看代码吧。

状态转移方程：dp[i+val[u]][v]=min(dp[i][u]+map[u][v],dp[i+val[u]][v])

这里的val[u]表示城市i被压缩状态后的数值，i是未从u走到v的状态，dp[i][u]就是未走的花费，那么i+val[u]就是已从u走到v的状态，dp[i][u]+map[u][v]就是已走的花费，用它去更新dp[i+val[u]][v]即可。

示例程序

Problem : 3001 ( Travelling ) Judge Status : Accepted RunId : 20826751 Language : GCC Code Len : 1549 B Code Render Status : Rendered By HDOJ GCC Code Render Version 0.01 Beta #include <stdio.h> #include <string.h> #define MAX 0x3f3f3f3f int dp[59050][10],map[10][10],val[11]={1,3,9,27,81,243,729,2187,6561,19683,59049}; int min(int x,int y) { if(x<y) { return x; } else { return y; } } int main() { int n,m,i,i1,i2,ans,u,v,w,flag; while(scanf("%d %d",&n,&m)!=EOF) { memset(dp,MAX,sizeof(dp)); memset(map,MAX,sizeof(map)); ans=MAX; for(i=1;m>=i;i++) { scanf("%d %d %d",&u,&v,&w); u--; v--; map[u][v]=min(map[u][v],w); //防止重边 map[v][u]=map[u][v]; } for(i=0;n>i;i++) //对于每个城市都只经过一次，等同于我们对每个城市设置起点 { dp[val[i]][i]=0; } for(i=1;val[n]>i;i++) //枚举各个城市经过多少次的状态 { flag=1; for(i1=0;n>i1;i1++) //相当于从一个城市到另一个城市的出发点 { if(i/val[i1]%3==0) //存在有城市一次都没经过 { flag=0; continue; } for(i2=0;n>i2;i2++) //相当于从一个城市到另一个城市的目的地 { if(i/val[i2]%3!=2) //当前城市已经经过2次不可再走 { dp[i+val[i2]][i2]=min(dp[i][i1]+map[i1][i2],dp[i+val[i2]][i2]); //状态转移方程 } } } if(flag==1) //如果有没经过的城市，肯定不能更新答案 { for(i1=0;n>i1;i1++) { ans=min(ans,dp[i][i1]); } } } if(ans==MAX) { ans=-1; } printf("%d\n",ans); } return 0; }