最短Hamilton路径

题目

题目链接

题解

状压dp。

f[i][j]表示从0点按照路径i走到j点的最短距离。其中i为二进制数，1表示走过某点，0表示未走过某点，比如10010表示经过了1、4两个点，而不经过0、2、3点。

状态转移为：假设沿路径i走到j点经过k点，且由k直接到j，那么由于k到j的距离是固定的，所以想要0到j的距离最短，只要保证0到k的距离最短即可，求出0到k的距离加上k到j的距离，取其中最小者就是0到j的最短距离。

说实话，不明白为什么状态从00000每次加一遍历到11111就是正确的？如何（不严谨地）证明其合理性？很显然，如果将遍历的方式改为从11111每次减一到00000，那么结果就是错误的。（加一顺序遍历得到的每一个状态都可以由之前算得的状态计算出来）

代码

#include
using namespace std;
const int N = 20;
int n;
int w[N][N];
int f[1n;
	for(int i = 0;i w[i][j];
			
	memset(f, 0x3f, sizeof f);
	f[1][0] = 0; // 从0点走到0点的状态为（000001），距离为0
	for(int i = 0;i