题解：P10447 最短 Hamilton 路径

$\textbf{Description}$

给定一张 $n$ 个点的带权无向完全图，求出从 $0$ 到 $n-1$ 经过每个点恰好一次的最短路径。

$\textbf{Solution}$

$\textbf{Brute Force}$

考虑最朴素的做法。

由于每个点只能经过一次，所以可以枚举 $n$ 个点的全排列。对于每个全排列，遍历每个点，计算路径长度。最后找到最短的路径长度即可。

时间复杂度：$O(n\cdot n!)$，$20!$ 铁定是会 TLE 的。

$\textbf{DP}$

$n\le20$ 的数据范围，除了搜索，指数级别的算法也是可以的。可以考虑状态压缩 DP。

无后效性：每个点只能经过一次，后面的状态不会影响前面的状态；
最优子结构：每个状态的转移都是类似的，都是从前一个状态加上边权得到现有状态。

考虑已经经过了一些点到达了节点 $u$，现在再走一个点到达 $v$。由于每个点只能经过一次，我们不可避免地要关心每个点是否经过。但是与暴力做法相比，经过了这些点之后，就不再关心这些点经过的顺序。

状态表示

首先，我们要在任何时刻都可以表示已经经过了哪些点。可以使用一个 $n$ 位二进制数 $S$，第 $i\,(0\le i

仅仅这样一个二进制数够了吗？假如已经知道通过的点集为 $S$，枚举了下一个点，但是无法得知是从哪个点过来的。

所以，我们还需要记录最后一个经过的点 $v$。

综上所述，状态标识为 $f(S,v)$，表示已经通过了 $S$ 中为 $1$ 的点，且最后一个点（当前所在的点）为 $v$。

状态转移

显然，最外层循环要枚举 $S$，然后第二层循环枚举 $v$。然后需要进行一个特判。$v$ 是已经经过了的，但是如果 $S$ 中的第 $v$ 位为 $0$（即表示还没有经过），这是不合逻辑的，需要跳过。

现在，我们想要得到 $f(S,v)$ 的值。$v$ 是最后经过的点，那么我们需要知道，$v$ 是从哪个点过来的。所以可以在 $S$ 内枚举点 $u$，表示 $u\to v$。当然，可以特判 $u\not=v$，但是本题中保证 $u\to v$ 的边权为 $0$，所以可以不用判断。~~不判断比判断快了 0.2s。~~

接下来，$f(S,v)\gets f(S-\{v\},u)+g(u,v)$（$g(x,y)$ 表示 $x\to y$ 的边权），意义即为从没有经过 $v$ 的状态且最后一个点为 $u$，然后到达 $v$，此间路径长度增加了 $g(u,v)$。由于 $v\in S$，所以 $S-\{v\}$ 可以写成 S-(1<<v)。

综上所述，
$$ f(S,v)=\min\limits_{u\in S}\Big(f(S-\{v\},u)+g(u,v)\Big) $$

初始化

开始时 $f$ 赋值为 $+\infty$，但是 $f(1,0)\gets0$。因为初始在 $0$ 点，$S_{(2)}=000\cdots01_{(2)}=1_{(10)}$，$v=0$，此时的路径长度为 $0$。

转移细节

首先，$S\sub T$ 这一偏序关系被 $S

$S$ 枚举要从 $0\sim2^n-1$ 吗？当然，结果为 $2^n-1$ 是确定的，但是从哪里开始呢？

$S=0_{(10)}$：$v$ 一个值也找不到，没用；
$S=1_{(10)}$：初始化过了，没用；
$2\,|\,S_{(10)}$：$S_{(2)}=\cdots0_{(2)}$，$0$ 号点未经过，没用。

所以最外层循环可以这样写：for (int S = 3; S < 1 << n; S += 2)，比 ++S 快了许多。

结果

要通过每个点恰好一次并且最后到达点 $n-1$，所以 $S=\underbrace{111\cdots111}_{n\text{个}1}$，$v=n-1$。

时空复杂度：

时间复杂度：$O(n^2\cdot2^n)$；
空间复杂度：$O(n\cdot2^n)$。

$\textbf{Code}$

#include <vector>
#include <cstring>
#include <iostream>
#define min(a,b) ((a)<(b)?(a):(b))

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  int n; std::cin >> n;
  std::vector<std::vector<int>> g(n, std::vector<int>(n));
  std::vector<std::vector<int>> f(1 << n, std::vector<int>(n, 2e9)); // 初始值赋为每个元素为 +∞
  // f[S][i] 表示经过了 S 中为 1 的点，且最后一个点为 i 的最短路径
  for (auto &x : g) for (auto &y : x) std::cin >> y; // 读入边权
  f[1][0] = 0; // 初始化
  for (int S = 3; S < 1 << n; S += 2) // 加速优化
    for (int v = 1; v < n; ++v) if (S >> v & 1) // v ∈ S 时转移
      for (int u = 0; u < n; ++u)
        if (S >> u & 1) f[S][v] = min(f[S][v], f[S - (1 << v)][u] + g[u][v]); // u ∈ S 时转移
  std::cout << f[(1 << n) - 1][n - 1] << std::endl; // 最终结果。(1<<n)-1 就是 n 个 1 的二进制数
  return 0;
}