HDU-3001 Travelling

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<<27
using 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
");
        else
            printf("%d
",ans);
    }
    return 0;
}
/*
4 5
1 4 1
1 2 1
1 3 2
4 3 10
2 3 10
*/
 