NK996D 最短Hamilton路径（状压dp）

链接：https://ac.nowcoder.com/acm/contest/996/D
来源：牛客网
 

题目描述

给定一张 n(n≤20)(n \leq 20)(n≤20) 个点的带权无向图，点从0∼n−10 \sim n-10∼n−1标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入描述:

第一行一个整数n。
接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（一个不超过10710^7107的正整数，记为a[i,j]）。
对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且a[x,y]+a[y,z]≥a[x,z]a[x,y]+a[y,z] \geq a[x,z]a[x,y]+a[y,z]≥a[x,z]。

输出描述:

一个整数，表示最短Hamilton路径的长度。

示例1

输入

4
0 2 1 3
2 0 2 1
1 2 0 1
3 1 1 0

输出

4

说明

从0到3的Hamilton路径有两条，0-1-2-3和0-2-1-3。前者的长度为2+2+1=5，后者的长度为1+2+1=4

dp[i][S]表示当前位置为 i ，状态为 S 的最小路径和，如果要求哈密顿回路需要遍历dp[i][(1 << n) - 1] + mp[0][i]，求最小值

两种更新方法：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 21;
 
int mp[N][N];
int dp[(1 << 21)][N];
 
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                scanf("%d", &mp[i][j]);
            }
        }
        memset(dp, inf, sizeof(dp));
        dp[1][0] = 0;
        for(int i = 1; i < (1 << n); ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if((i >> j) & 1)
                {
                    for(int k = 0; k < n; ++k)
                    {
                        if((i >> k) &1)
                        {
                            dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + mp[k][j]);
                        }
                    }
                }
            }
        }
        cout<<dp[(1 << n) - 1][n - 1]<<'\n';
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 21;

int mp[N][N], n;
int dp[N][(1 << 20)];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            scanf("%d", &mp[i][j]);
        }
    }
    memset(dp, inf, sizeof(dp));
    dp[0][1] = 0;
    int bit = (1 << n);
    for(int S = 1; S < bit; ++S)
    {
        for(int i = 0; i < n; ++i)
        {
            if(S & (1 << i))
            {
                for(int j = 0; j < n; ++j)
                {
                    if(!(S & (1 << j)) && mp[i][j])
                    {
                        dp[j][S | (1 << j)] = min(dp[j][S | (1 << j)], dp[i][S] + mp[i][j]);
                    }
                }
            }
        }
    }
    cout<<dp[n - 1][bit - 1]<<'\n';
    return 0;
}