首页 > 代码库 > HDU-3001 Travelling

HDU-3001 Travelling

2024-07-15 13:30:54   222人阅读

    http://acm.hdu.edu.cn/showproblem.php?pid=3001    

从任何一个点出发，去到达所有的点，但每个点只能到达2次，使用的经费最小。三进制   

          Travelling

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3541    Accepted Submission(s): 1106


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
从任何一个点出发，去到达所有的点，但每个点只能到达2次，使用的经费最小。三进制。0,1,2.0代表0次，1,1次，2,2次。
dp[i][j]表示i状态到达j城市。
time[i][j]表示i状态到达j城市的次数，就像十进制求余求个位所得。
首先枚举所有的i状态，到达j个城市，在到达下一个城市。
 dp[p][k]=min(dp[p][k],dp[i][j]+dis[j][k]);p是一个城市的状态，i+s[k]所得，s[k]是成倍数所以加起来就是下一个的状态。k是下一个城市。flag去验证是否状态已经是每个城市都到达。
注意要排除重边的情况。
#include<iostream>#include<cstring>#include<cstdio>#define inf 1<<27using namespace std;int dis[20][20],dp[59049][20],s[20];int n,time[59049][20];void init(){    int temp,i,j;    s[1]=1;    for(i=2; i<=n+1; i++)        s[i]=s[i-1]*3;    for(i=1; i<=s[n+1]; i++)    {        temp=i;        for(j=1; j<=n; j++)        {            time[i][j]=temp%3;//模拟十进制取余求个数的方法。            temp=temp/3;        }    }}int main(){    int i,a,b,c,k,m,j,ans,flag;    while(~scanf("%d%d",&n,&m))    {        ans=inf;        for(i=0; i<59049; i++)        {            for(j=0; j<20; j++)                dp[i][j]=inf;        }        memset(s,0,sizeof(s));        memset(time,0,sizeof(time));        for(i=1; i<=n; i++)            for(j=1; j<=n; j++)            {                if(i==j)                    dis[i][j]=0;                else                    dis[i][j]=inf;            }        for(i=1; i<=m; i++)        {            scanf("%d%d%d",&a,&b,&c);            dis[a][b]=dis[b][a]=min(dis[a][b],c);//防止有重边。        }          init();        for(i=1; i<=n; i++)            dp[s[i]][i]=0;//起点位置初始化为0.        for(i=1; i<s[n+1]; i++)        {            flag=1;//各点是否全部已经到了。            for(j=1; j<=n; j++)//当前到的这个城市。            {                if(time[i][j]==0)//该状态不可能都这个城市。                {                    flag=0;                    continue;                }                for(k=1; k<=n; k++)//到下一个城市。                {                    if(time[i][k]==2||j==k)//如果等于2，就不可以。                        continue;                    int p=i+s[k];//到达下个城市的状态。                dp[p][k]=min(dp[p][k],dp[i][j]+dis[j][k]);                }            }            if(flag)            {                for(j=1; j<=n; j++)                {                 ans=min(ans,dp[i][j]);                }            }        }        if(ans==inf)            printf("-1\n");        else            printf("%d\n",ans);    }    return 0;}/*4 51 4 11 2 11 3 24 3 102 3 10*/

 

 


联系
我们