题目描述

给定一张 $n$ 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 $Hamilton$ 路径。

$Hamilton$ 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数 $n$ 。

接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离（记为 $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]$ 。

输出格式:
输出一个整数，表示最短 $Hamilton$ 路径的长度。

数据范围:
$1\leq n\leq 20$
$0\leq a[i,j] \leq 107$

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

算法0

(朴素算法) $O(n\times n!)$

$n\leq 20$ ，肯定会爆。

算法1

(二进制状压) $O(n^2 \times 2^n)$

看到数据范围就知道一定是状压DP。因为实在是太有特点了hh。

二进制状态压缩，即将一个长度为 $len$ 的 bool 数组用一个 $len$ 位二进制整数表示出来的方法。
有一些 方便装B 好用的技巧：

(i>>j)&1 = 取出整数 i 在二进制下的第 j 位
i&((1<<j)-1) = 取出整数 i 在二进制下的后 j 位
i xor (1<<j) = 将整数 i 在二进制下的第 j 位取反(~)
i|(1<<j) = 将整数 i 在二进制下的第 j 位赋值为 1 。
i&(~(1<<j)) = 将整数 i 在二进制下的第 j 位赋值为 0 。

$e_{i,j}$ => i 到 j 的距离
$dp_{i,j}$ => 目前的[状态]对应的二进制数为 i (如果第 k 位 $(1\leq k\leq i的长度)$ 为 1 ，表示第 k 个点被经过了)，并且现在正在 j 点。

状态压缩方程:

$$dp_{i,j} = \min( dp_{i,j}, dp_{i{xor}(1<<j),k})$$

C++ 代码

//2021/6/2

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int ma=25;

int e[ma][ma],dp[1<<20][ma];

int n; 

int main(void)
{
    scanf("%d",&n);

    for(register int i=0;i<n;i++)
    {
        for(register int j=0;j<n;j++)
        {
            scanf("%d",&e[i][j]);
        }
    }

    memset(dp,0x3f,sizeof(dp));

    dp[1][0]=0;

    for(register int i=1;i<(1<<n);i++)
    {
        for(register int j=0;j<n;j++)//当前正在考虑的点
        {
            if(i>>j&1)//如果整数i在二进制下的第j位等于1 , 也就是说可以从 j 点到达 i 点
            {
                for(register int k=0;k<n;k++)//就枚举到达 j 的点
                {
                    dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+e[k][j]);//状压方程 ↑ ↑ ↑
                }
            }
        }
    }

    printf("%d\n",dp[(1<<n)-1][n-1]);

    return 0;
}