什么是哈密尔顿路径
哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable
graph）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian
cycle），含有图中所有顶点的路径称作哈密顿路径（Hamiltonian path）。
天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。
这个问题和著名的七桥问题的不同之处在于，过桥只需要确定起点，而不用确定终点。哈密顿问题寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。
实现：
// hamilton路径标签：图论,终点,哈密顿,int,路径,给定,hamilton,模板 From： https://blog.51cto.com/u_14682436/6054496
int f[1 << 20][20];
int hamilton(int n, int weight[20][20]) {
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
for (int i = 1; i < 1 << n; i++)
for (int j = 0; j < n; j++)
if (i >> j & 1)
for (int k = 0; k < n; k++)
if (i >> k & 1)
f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + weight[k][j]);
return f[(1 << n) - 1][n - 1];
}