hdu 3001 Travelling (3进制TSP)

 因为每个城市允许访问两次，所以要将经典的TSP问题转化为3进制，即这个地方没访问，访问一次，两次。

状态转移是一样的，我们预处理出所有状态下每一位对应的数字。还要注意重边

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define inf 0x3f3f3f3f
#define maxn 177148
using namespace std;

int map[12][12];
int dp[maxn][12];
int dig[maxn][12];
int tri[12] ={1,3,9,27,81,243,729,2187,6561,19683,59049,177147};

int main()
{
    int n,m;

    for(int i=0;i<177148;i++)
    {
        int t=i;
        for(int j=0;j<=10;j++)
        {
            dig[i][j]=t%3;
            t/=3;
            if(t==0)break;
        }
    }


    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int ans=inf;
        memset(map,0x3f,sizeof map);

        while(m--){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(c<map[a][b])map[a][b]=map[b][a]=c;
        }
        memset(dp,0,sizeof dp);

        for(int i=0;i<tri[n+1];i++)
        {
            bool visall=true;
            for(int j=1;j<=n;j++)//找到一个
            {
                if(dig[i][j])
                {
                    if(i==tri[j])//如果第一个经过j
                    {
                        dp[i][j]=0;
                    }
                    else
                    {
                        dp[i][j]=inf;
                        for(int k=1;k<=n;k++)//枚举另外一个点
                        {
                            if(dig[i][k] && k!=j && map[k][j]!=inf)
                            {
                                dp[i][j]=min(dp[i][j],dp[i-tri[j]][k]+map[k][j]);
                            }
                        }
                    }
                }
                else visall=false;
            }
            if(visall)
            {
                for(int j=1;j<=n;j++)
                ans=min(ans,dp[i][j]);
            }
        }

        if(ans==inf)printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}

hdu 3001 Travelling (3进制TSP)

原文：http://blog.csdn.net/u010709592/article/details/19092231