Description

给定一张 n 个点的带权无向完全图，求出从 0 到 n − 1 经过每个点恰好一次的最短路径。 ## Solution ### Brute Force 考虑最朴素的做法。

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

时间复杂度：O(n ⋅ n!)，20! 铁定是会 TLE 的。 ### DP n ≤ 20 的数据范围，除了搜索，指数级别的算法也是可以的。可以考虑状态压缩 DP。

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

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

状态表示

首先，我们要在任何时刻都可以表示已经经过了哪些点。可以使用一个 n 位二进制数 S，第 i (0 ≤ i < n) 位为 1 则表示这个点已经经过，为 0 则表示这个点尚未经过。

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

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

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

状态转移

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

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

接下来，f(S, v) ← f(S − {v}, u) + g(u, v)（g(x, y) 表示 x → y 的边权），意义即为从没有经过 v 的状态且最后一个点为 u，然后到达 v，此间路径长度增加了 g(u, v)。由于 v ∈ S，所以 S − {v}​ 可以写成 S-(1<<v)。 综上所述， #### 初始化 开始时 f 赋值为 +∞，但是 f(1, 0) ← 0。因为初始在 0 点，S(2) = 000⋯01(2) = 1(10)，v = 0，此时的路径长度为 0。 #### 转移细节 首先， 这一偏序关系被 S < T 包含，所以可以从小到大枚举每一个 S。

S 枚举要从 0 ∼ 2n − 1 吗？当然，结果为 2n − 1 是确定的，但是从哪里开始呢？

  • S = 0(10)：v 一个值也找不到，没用；
  • S = 1(10)：初始化过了，没用；
  • 2 | S(10)：S(2) = ⋯0(2)，0 号点未经过，没用。

所以最外层循环可以这样写：for (int S = 3; S < 1 << n; S += 2)，比 ++S 快了许多。 #### 结果 要通过每个点恰好一次并且最后到达点 n − 1，所以 个，v = n − 1。 #### 时空复杂度： - 时间复杂度：O(n2 ⋅ 2n)； - 空间复杂度：O(n ⋅ 2n)。 ## Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}