Hamilton回路 旅行商TSP问题 /// dp oj1964

题目大意：

给出一个n个顶点的无向图，请寻找一条从顶点0出发，遍历其余顶点一次且仅一次、最后回到顶点0的回路——即Hamilton回路。

Input

多测试用例。每个测试用例：

第一行，两个正整数 n 和 e ，0 < n ≤ 21 ，n < e < n×n/2 ，表示该无向图的顶点个数，以及边的数量。顶点编号是0～n-1

第二行至e+1行，每行3个非负整数 u , v 和 w ，分别表示顶点u与顶点v之间有一条边，其权值为w 。

Output

如果存在多条Hamilton回路，请输出长度最小的回路的路径长度。

如果不存在Hamilton回路，请输出 no Hamilton circuit

Sample Input

4 5
0 1 50
0 3 9
0 2 3
1 2 3
1 3 13

Sample Output

28

 

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define N 21

using namespace std;

int n,m,G[N][N],dp[<<N][N];

void solve()

{

    memset(dp,INF,sizeof(dp));

    int ed=(<<n)-; // 点为0~n-1

    dp[][]=; // 初始状态0点已走过且位于0点

    for(int i=;i<=ed;i++) /// 枚举顺推下去的所有状态

        for(int j=;j<n;j++) { /// 枚举该状态下要去的点

            if(<<j&i) continue; // 若该状态已经曾走过j点 则忽略

            for(int k=;k<n;k++) { /// 枚举j点的前驱点

                if(<<k&i) // 若该状态曾经走过k点 则更新 不曾走过则忽略

                dp[<<j|i][j]=min(dp[<<j|i][j],dp[i][k]+G[k][j]);

            } /// 由i状态且最后位于k点 延伸到 j点走过且最后位于j点的状态

        }

    int ans=INF;

    for(int i=;i<n;i++) /// 每个点都走过且最后位于i 再加上i点回到0点的路径

        ans=min(ans,dp[ed][i]+G[i][]);

    if(ans==INF) printf("no Hamilton circuit\n");

    else printf("%d\n",ans);

//    for(int i=1;i<=ed;i++){

//        for(int j=0;j<n;j++){

//            if(dp[i][j]==INF) printf("-1 ");

//            else printf("%d ",dp[i][j]);

//        }printf("\n");

//    }

}

int main()

{

    while(~scanf("%d%d",&n,&m)) {

        memset(G,INF,sizeof(G));

        while(m--) {

            int u,v,w; scanf("%d%d%d",&u,&v,&w);

            G[u][v]=G[v][u]=min(G[u][v],w);

        }

        solve();

    }

    return ;

}