原题链接：91. 最短Hamilton路径
解题思路
首先想下暴力算法，这里直接给出一个例子。
比如数据有 55 个点，分别是 0,1,2,3,4
那么在爆搜的时候，会枚举一下六种路径情况（只算对答案有贡献的情况的话）：
case 1: 0→1→2→3→4
case 2: 0→1→3→2→4
case 3: 0→2→1→3→4
case 4: 0→2→3→1→4
case 5: 0→3→1→2→4
case 6: 0→3→2→1→4
那么观察一下 case 1 和 case 3，可以发现，我们在计算从点 0 到点 3 的路径时，其实并不关心这两中路径经过的点的顺序，而是只需要这两种路径中的较小值，因为只有较小值可能对答案有贡献。
所以，我们在枚举路径的时候，只需要记录两个属性：当前经过的点集，当前到了哪个点。
而当前经过的点集不是一个数。观察到数据中点数不会超过 20，我们可以用一个二进制数表示当前经过的点集。其中第 i 位为 1/0 表示 是/否 经过了点 i。
然后用闫式 dp 分析法考虑 dp
状态表示：f[state][j]。其中 state 是一个二进制数，表示点集的方法如上述所示。
集合：经过的点集为 statestate，且当前到了点 jj 上的所有路径。
属性：路径总长度的最小值
状态计算：假设当前要从点 k 转移到 j。那么根据 Hamilton 路径的定义，走到点 k 的路径就不能经过点 j，所以就可以推出状态转移方程
f[state][j] = min{f[state ^ (1 << j)][k] + w[k][j]}
其中w[k][j]表示从点 k 到点 j 的距离，^表示异或运算。
state ^ (1 << j) 是将 state 的第 j 位改变后的值，即
如果 state 的第 j 位是 1 那么将其改为 0
否则将 state 的第 j 位改为 1
由于到达点 j 的路径一定经过点 j，也就是说当 state 的第 j 位为 1 的时候，f[state][j] 才可以被转移，所以 state ^ (1 << j) 其实就是将 state 的第 j 位改为 0，这样也就符合了 走到点 k 的路径就不能经过点 j 这个条件。
所有状态转移完后，根据 f[state][j] 的定义，要输出 f[111⋯11(n个1)][n−1]。
那么怎么构造 n 个 1 呢，可以直接通过 1 << n 求出 100⋯0(n个0) ，然后减一即可。
时间复杂度
枚举所有 state 的时间复杂度是 O(2n)
枚举 j 的时间复杂读是 O(n)
枚举 k 的时间复杂度是 O(n)
所以总的时间复杂度是 O(pow(n,2) * pow(2,n))
样例代码
#include <stdio.h>
#include <string.h>
const int N = 20;
const int M = 1 << 20; // 一共最多有 20 个 1 种状态
int n;
int w[N][N]; // 存每两个点之间的距离
int f[M][N]; // 上述 f[state][j]
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &w[i][j]);
memset(f, 0x3f, sizeof f); // 由于要求最小值，所以这里将 f 初始化为正无穷会更好处理一些
f[1][0] = 0; // 因为题目要求从点 0 出发，所以这里要将 经过点集为 1，当前到达第 0 个点 的最短路径初始化为 0
for (int state = 1; state < 1 << n; state ++ ) // 从 0 到 111...11 枚举所有 state
if (state & 1) // state 必须要包含起点 1
for (int j = 0; j < n; j ++ ) // 枚举所有 state 到达的点
if (state >> j & 1) // 如果当前点集包含点 j，那么进行状态转移
for (int k = 0; k < n; k ++ ) // 枚举所有 k
if (state ^ 1 << j >> k & 1) // 如果从当前状态经过点集 state 中，去掉点 j 后，state 仍然包含点 k，那么才能从点 k 转移到点 j。
// 当然这个 if 也可以不加，因为如果 state 去掉第 j 个点后，state 不包含点 k 了，
// 那么 f[state ^ 1 << j][k] 必然为正无穷，也就必然不会更新 f[state][j]，所以去掉也可以 AC。
if (f[state ^ 1 << j][k] + w[k][j] < f[state][j]) // 由于 >> 和 << 的优先级要比 ^ 的优先级高，所以这里可以将 state ^ (1 << j) 去掉括号。
f[state][j] = f[state ^ 1 << j][k] + w[k][j];
printf("%d
", f[(1 << n) - 1][n - 1]); // 最后输出 f[111...11][n-1]
return 0;
}
作者：垫底抽风
链接：https://www.acwing.com/solution/content/15328/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。