状态压缩 DP 选讲

约 960 字大约 3 分钟

2026-01-25

例题：最短 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

Input

Output

例题分析

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

设 $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

mask-dp.cc
#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;
}

Codeforces

牛客

寒假训练营-2026