---
url: /algo/46ka6a24/index.md
---
## 例题：最短 Hamilton 路径

### 题目描述

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

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

### 输入格式

第一行输入整数 $n$。

接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i-1$ 到 $j-1$ 的距离（记为 $a\[i-1,j-1]$）。

对于任意的 $x,y,z$，数据保证 $a\[x,x]=0,a\[x,y]=a\[y,x]$ 并且 $a\[x,y]+a\[y,z] \geqslant a\[x,z]$。

对于所有测试数据满足 $1 \leqslant n \leqslant 20$，$0 \leqslant a\[i,j] \leqslant 10^7$

### 输出格式

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

### 输入输出样例 #1

::: code-tabs
@tab Input

```txt
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
```

@tab Output

```txt
18
```

:::

## 例题分析

这个题目我们先做一个基本的认识，即我们有下面的（有点奇怪）的图成立：

```mermaid
graph LR
    A((0)) <-- 2 --> B((1))
    A <-- 4 --> C((2))
    A <-- 5 --> D((3))
    A <-- 1 --> E((4))

    B <-- 6 --> C
    B <-- 5 --> D
    B <-- 3 --> E

    C <-- 8 --> D
    C <-- 3 --> E

    D <-- 5 --> E

    %% style S fill:#dfd
    %% style D fill:#fdd
```

设 $d\[u]\[v]=d(u,v)$ 表示 $u\rightarrow v$ 点距离，既然要走遍所有的点，那么我们设计状态 $f\[i]\[j]$ 表示已经走完所有点后为最终位置 $j$ 的最短路，其中我们令 $i$ 表示走的点的状态。

那么怎么表示状态呢？这就想到了用二进制来表示其状态，设 $i$ 的二进制位的 $0$ 位表示没有走过的路，$1$ 表示已经走过的路，即 $01101\_2$ 表示 $0,2,3$ 点已经走过，而 $1,4$ 点还未走过。最后到点 $4$ 的情况就是访问 $f\[11111\_2]\[4]$ 的值，即 $f\[31]\[4]$。

那么接下来从内循环开始枚举点位，边界条件就是 $f\[1]\[0]=0$ 表示在 $0$ 处最短路，枚举点位 $1\sim 4$

$$
f\[00011\_2]\[1]=f\[3]\[1]=\min(f\[3,1],f\[3]\[1]+d\[0]\[1])\\
f\[00101\_2]\[2]=f\[5]\[2]=\min(f\[5,1],f\[5]\[1]+d\[0]\[2])\\
f\[01001\_2]\[3]=f\[9]\[3]=\min(f\[7,1],f\[7]\[1]+d\[0]\[3])\\
f\[10001\_2]\[4]=f\[17]\[4]=\min(f\[17,1],f\[17]\[1]+d\[0]\[4])
$$

然后考虑从中循环考虑从点位 ${0,1,2,3,4}\rightarrow {1,2,3,4}$ 也就是说，$1$ 可能从 $0,2,3,4$ 这些点转移过来，下面是一些例子：

$$
f\[00111\_2]\[1] = \min(f\[00111\_2]\[1],f\[00101\_2]\[2]+d\[2]\[1])\\
f\[01111\_2]\[1] = \min(f\[01111\_2]\[1],f\[01101\_2]\[2]+d\[2]\[1])\\
f\[01101\_2]\[3] = \min(f\[00101\_2]\[3],f\[00101\_2]\[2]+d\[2]\[3])\\
\cdots
$$

最后在外层循环枚举所有状态，也就是从 $1\sim 2^{n}$。此外，有些状态是不合法的，例如 $f\[10001\_2]\[3]$ 因为第三位为 $0$，但是 $f\[i]\[j]$ 又表示到达 $3$ 的最短路，所以枚举到 $f\[10001\_2]\[3]$ 状态时直接 `break`。

## Full Code

```cpp title="mask-dp.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
array<array<int, 20>, 1 << 21> dp;              // dp 表
array<array<int, 25>, 25> arr;                  // 输入表
int main()
{
    int n;
    cin >> n;
    for (auto &i : dp)
    {
        fill(i.begin(), i.end(), 0x3f3f3f3f);   // 猜猜为什么不用 INT_MAX?
    }
    dp[1][0] = 0;                               // 初始状态
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];                   // 读入数据
        }
    }
    for (int i = 0; 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 && k != j)
                    {
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + arr[k][j]);
                    }
                }
            }
        }
    }
    cout << dp[(1 << n) - 1][n - 1];
    return 0;
}
```

## 复杂度分析

时间复杂度 $O(n^2\cdot 2^n)$; 空间复杂度 $O(n\cdot 2^n)$。

## 课后练习

[洛谷P1012：拼数](https://www.luogu.com.cn/problem/P1012)