hdu3001Travelling

参考了别人的代码   https://blog.csdn.net/u010372095/article/details/38474721

深感自己的弱小

这是tsp问题，和基本的tsp问题没什么大的区别，唯一的区别就是采用了三进制

原来的二进制的某一位只能表示到达或没到达过，现在加了三进制，就能表示到达过几次了

tsp问题网上的讲解我推荐这一篇    http://www.360doc.com/content/17/0826/11/36546539_682232069.shtml

我个人感觉讲的算是很详细了，剩下的就是代码实现了。

#include<iostream>

#include<queue>

#include<cstring>

#include<vector>

#include<cstdio>

#include<cmath>

#include<map>

#include<string>

using namespace std;

#define ll long long

#define se second

#define fi first

#define oo 0x3fffffff

int n,m;

int dp[][];

int dis[][];

int three[];

int in[];

int tothree(int n);

int main()

{

    in[] = ;

    for(int i = ; i <= ; ++i)

        in[i] = in[i-]*;

    while(scanf("%d%d",&n,&m) != EOF)

    {

        for(int i = ; i < n; ++i)

        {

            for(int j = ; j < in[n]; ++j)

                dp[i][j] = -;

            for(int j = ; j < n; ++j)

                dis[i][j] = -;

        }

        //cout << 1 << endl;

        for(int i = ; i < m; ++i)

        {

            int a,b,c;

            scanf("%d%d%d",&a,&b,&c);

            a --; b --;

            if(dis[a][b] == -)

                dis[a][b] = dis[b][a] = c;

            else

                dis[a][b] = dis[b][a] = min(dis[a][b],c);

        }

        int minn = -;

        for(int l = ; l < in[n]; ++l)

        {

            int k = tothree(l);

            for(int i = ; i < n; ++i)

            {

                if(three[i])

                {

                    if(k == )

                        dp[i][l] = ;

                    if(dp[i][l] == -)

                        continue;

                    if(k == n)

                    {

                        if(minn == -) minn = dp[i][l];

                        else minn = min(minn,dp[i][l]);

                    }

                    for(int j = ; j < n; ++j)

                    if(i != j && three[j] <  && dis[i][j] != -)

                    {

                        int tog = l + in[j];

                        if(dp[j][tog] == -)

                            dp[j][tog] = dp[i][l] + dis[i][j];

                        else

                            dp[j][tog] = min(dp[j][tog],dp[i][l] + dis[i][j]);

                    }

                }

            }

        }

        printf("%d\n",minn);

    }

}

int tothree(int n)

{

    int k = ;

    for(int i = ; i < ; ++i)

    {

        three[i] = n%; n/=; if(three[i]) k++;

    }

    return k;

}