P10447 最短 Hamilton 路径 题解
Published:
P10447 最短 Hamilton 路径 题解
题意：给定一张有向带权图（$n \le 20$）求点 $0$ 到点 $n-1$ 的最短哈密顿路径。
这是一道状压 DP 模板题。在状态压缩 DP 中，我们将一个集合压成一个二进制数。
设 $f_{u,i}$ 为已经走了集合 $u$ 中的节点，且现在在点 $i$ 的最短路。枚举路径上 $i$ 的前一个点 $j$ 进行转移。
时间复杂度 $O(n^2 2^n)$。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
template<typename T>
void cmin(T &x, T y) {
x = min(x, y);
}
const int N = 20;
int n;
int dis[N][N];
int f[1 << N][N];
int main() { ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> dis[i][j];
uint tot = (1 << n) - 1;
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for (uint u = 0; u <= tot; u++)
for (int i = 0; i < n; i++)
if (u & (1 << i))
for (int j = 0; j < n; j++)
if ((u ^ (1 << i)) & (1 << j))
cmin(f[u][i], f[u ^ (1 << i)][j] + dis[j][i]);
cout << f[tot][n-1] << endl;
return 0;
}