最短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<bits/stdc++.h>
using namespace std;
const int N = 20;
int n;
int w[N][N];
int f[1<<N][N]; 
int main()
{
	cin>>n;
	for(int i = 0;i < n;i ++)	
		for(int j = 0;j < n;j ++)
			cin>>w[i][j];
			
	memset(f, 0x3f, sizeof f);
	f[1][0] = 0; // 从0点走到0点的状态为（000001），距离为0
	for(int i = 0;i < (1 << n);i ++)
		for(int j = 0;j < n;j ++) // 枚举目的地，即最后一个点
			if((i >> j) & 1) // j点必须要走过才行
				for(int k = 0;k < n;k ++) // 枚举倒数第二个点
					if(((i - (1 << j)) >> k) & 1) // 除去j点后，k点必须走过才行
						f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
	
	cout << f[(1 << n) - 1][n-1] << endl;

	return 0;
}