旅行商问题

给一个 \(n (n \leq 20)\) 个点的非负权有向图，求经过所有点的回路的最短长度。其中，每个点可以经过多次。

给定的边并不一定是最短的距离，需要先把邻接矩阵转换为距离矩阵。

本题中，DP 状态有集合。尽管在 C++ 中可以使用 map <set <int>, int> 的方式来实现下标集合访问，但这样的话需要额外维护 \(O(n \cdot 2 ^ n)\) 的空间，并且每次下标访问会有 \(O(n \log n)\) 的代价。

对于一个较小的集合，我们可以用二进制串（类似于 bool 数组）来表示每个元素是否存在，这样的话我们就可以用 \([0, 2 ^ n)\) 的下标来使用数组维护集合状态。计算机本身就能很好地完成位运算，因此我们直接使用 int 即可。以下是某些可能的操作：

空集: 0
全集：(1 << n) - 1 \(= (2 ^ n - 1) = (\underbrace{111\dots1}_{n})_2\)
测试 \(i\) 是否在 mask 里: (mask >> i) & 1
往 mask 里插入/删除 \(i\)：mask ^ (1 << i)
- 无论之前是否存在，令其存在：mask | (1 << i)
- 无论之前是否存在，令其不存在：mask & (~(1 << i))
对全集取反：~mask & ((1 << n) - 1)，或者 mask ^ ((1 << n) - 1)
计算 mask 二进制中 \(1\) 的个数: __builtin_popcount(mask)
- 对于 long long，需要使用 __buitin_popcountll

举个例子，如果我们想枚举 mask 里的元素，你可以这么做：

for (int i = 0; i < n; i++) {
    if ((mask >> i) & 1) {
        // element i in mask
    }
}

位运算的运算优先级

位运算的优先级很低/很奇怪，在和其他运算写在一起时容易混淆。请多使用括号来避免结果有误。

在 DP 的时候我们可能需要关注 mask 之间的拓扑序，通常来说是一个集合的所有子集必须在这个集合之前。你可以采取