AcWing 91. 最短Hamilton路径
枚举 $n$ 个点的全排列，计算路径长度取最小值，时间复杂度位 $\mathcal{O}(n * n!)$。
使用二进制状态压缩 DP 可以优化到 $\mathcal{O}(n^2 * 2^n)$。
在任意时刻如何表示哪些点已经被经过，那些点没有被经过？
可以用一个 $n$ 位二进制数，若其第 $i$ 位 $(0 \le1 i < n)$ 为 $1$，则表示第 $i$ 个点已经被经过，反之未被经过。
在任意时刻还需要知道当前所处的位置，因此我们可以使用 $F[i, j] (0 \leq 1 i < 2^n, 0 \leq j < n)$ 表示 “点被经过的状态” 对应的二进制数为 $i$，且目前处于点 $j$ 时的最短路径。
在起点时，有 $F[1, 0] = 0$，即只经过了点 $0$ ($i$ 只有第 $0$ 位为 $1$)，目前处于起点 $0$，最短路长度为 $0$。
为了方便起见，我们将 $F$ 数组其他的值设为无穷大。
目标是 $F[(1 « n) - 1, n - 1]$，即经过所有点 ($i$ 的所有位都是 $1$)，处于终点 $n - 1$ 的最短路。
在任意时刻，有 $F[i, j] = \min {F[i \oplus (1 « j), k] + weight(k, j) }$，其中 $0\leq k < n$ 并且 $((i » j) \& 1)=1$，即当前时刻 “被经过的点的状态” 对应的二进制数为 $i$，处于点 $j$。
因为 $j$ 只能被恰好经过一次，所以一定是刚刚经过的，故在上一时刻 “被经过的点的状态”对应的二进制数的第 $j$ 位应该赋值为 $0$，也就是 $i \oplus (i « j)$。
另外，上一时刻所处的位置可能是 $i \oplus (1 « j)$中任意一个是 $1$ 的数位 $k$，从 $k$ 走到 $j$ 需经过 $weight(k, j)$ 的路程，可以考虑所有这样的 $k$ 取最小值。
完整代码：最短Hamiltion路径.cpp