题目描述
给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数n。
接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（记为a[i,j]）。
对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。
输出格式
输出一个整数，表示最短Hamilton路径的长度。
数据范围
$1 \le n \le20$
$0 \le a[i,j] \le 10^7$
输入样例：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例：
18
算法1
(暴力枚举) $O(n*n!)$
NP完全问题，相信纯暴力都可以写出，所以蒟蒻懒得写了
正解
正解思路(建议先看代码，不然有点难理解)
首先我们要思考如果让这个NP完全题目复杂度降低，那么可以优先考虑到使用位运算，状态压缩等解决思路。
然后接着思考，我们可以发现，我们所需要的不是整个方案，而只是方案最优解，所以我们只需要记录当前这个方案的最优解即可，那么我们考虑的状态，不久只有，在当前方案i中，目前抵达的点是j。
现在既然装填已经确定好了当前点j，那么这个j点是由哪一个状态移动而来的呢？我们可以选择k，也就是说我们的状态转移方程可以为
f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]//感谢楼下大佬们指出打字错误.
以上转移方程，weight数组为权值 ，也就是weight[k][j]是k点到j点的权值
i^(1<<j)的意思是，i 异或 1右移j位，具体来说就是i这个方案集合 xor 10……0,(其中1的位置在第j位)。
那么这个位运算有什么用处呢，第一点它是在判断第j位的情况，第二点位运算处理速度很快。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n,f[1<<20][21],i,j,k;
int weight[21][21];
int main()
{
ios::sync_with_stdio(false);//加快cin的读入速度，但是scanf将会不能用。
memset(f,0x3f,sizeof(f));//初始化最大值
cin>>n;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
cin>>weight[i][j];
f[1][0]=0;//第一个点是不需要任何费用的
for (i=1; i<(1<<n); i++)//i代表着是一个方案集合，其中每一个位置1和0，代表着这个点经过还是没有经过
for (j=0; j<n; j++)//枚举当前到了哪一个点
if ((i>>j & 1))//如果i集合中第j位是1，也就是到达过这个点
for (k=0; k<n; k++)//枚举到达j的点k
if ((i^(1<<j)) >> k & 1)//重点，判断k和j的条件，具体在上面解说
f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]);//选择最小值，也就是判断，k点到j点最优，还是以前的方案最优
cout<<f[(1<<n)-1][n-1];//输出最后的最优值
return 0;
}
这题不能用普利姆和克鲁斯卡尔吗
我觉得可以，但这道题给的是矩阵形式的输入，要手动转成无向图的输入形式
不能，那样只是保证一条总路径最短的连通图。与题目要求从0点到n-1路径最短不一样，用克鲁斯卡尔得出来的连通图可能还要走回头路（一条路走多遍）才能从起始点0走到终点n-1。
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
（完整版）
谢谢您
但是我发现，把
if ((i^(1<<j)) >> k & 1)这句话去掉也能AC是因为数据水吗？还是这个判断就是不必要的？
下面把$i$看成是一个集合。这个判断应该等价于$k\in i$(从集合$i$中去掉城市$j$不影响$k\in i$的真假，除非$k=j$，但是这种情况不会影响对答案的优化)。那么把这个
if去掉，就会导致满足$k\not \in i$的$k$参与答案优化。但是$f(\{x\},y)$这种状态是始终为无穷大的，归根到底也不会对答案有什么贡献，所以这个if是可以去掉的。各位大佬觉得呢……弟弟mathjax,{}记号炸了。上面说的f(x,y)是f[{x}][y]，其中x和y是两个不相同的城市。因为我们只对形如f[{a,b,c}][c]的状态进行更新，所以形如f[{x}][y],x!=y的状态始终是无穷大，不会影响答案。
您说的很对,因为考虑到本题目的最值性质,所以其实因为之前有过极值初始化,所以不需要考虑本问题,但是为了算法完整性,所以补上了这句话,
谢谢您
我学到了许多
memset(f,0x3f,sizeof(f));//初始化最大值
为什么是0x3f？
按字节初始化，相当于0x3f3f3f3f
谢谢
按字节初始化，0x3f3f3f3f的好处有两点，一是这个数字足够大，二是这个数字可以做加法，避免用int -max造成数据溢出的情况
请问这个条件我们能够获取到什么信息呢？或者说这题目少了这个条件是否还是这么做呢？
对于任意的 x,y,z，数据保证 a[x,y]+a[y,z]≥a[x,z]。
不影响求解，在算法竞赛进阶指南这本书中直接就没有这个条件，一样的代码。满足该三角不等式条件的是一类特殊的哈密顿问题。
okok谢谢谢谢
只能说tql，大佬
感谢大佬，终于懂了
看了你的终于懂了
为啥结果是[N-1]啊, 最后一步到其他的点不行吗
题目写了终点是n-1
想问一下，为什么循环时候是外层循环路径，内层循环终点的？如果反过来结论就是不对得了。这里我不是很理解，求大佬解答。
因为转移的时候需要用到的值总不能还未被更新过吧！
弱弱地问一句 纯暴力为啥是n*n！ 起点固定不应该是n！吗，更具体点应该是（n-1）！
同问，我也在想为啥暴力 会多乘一个n
爆搜枚举所有Hamilton路径 $O(n!)$ 的，每枚举到一种路径要 $O(n)$ 的算一下这个路径的长度，所以总的时间复杂度为 $O(n \times n!)$
原来如此😁
谢谢抽风
谢谢懂了！
想问一下题目中“其中第i行第j个整数表示点i到j的距离（记为a[i,j]）”什么意思啊，题目就是找最短的方案能理解，这个题目 第 i 行 当中 第 j 个整数 表示 点 i 到 j 的距离，这个点 i ，j 从何来啊,希望大佬给解释下
题目给了一个矩阵，表示某些点到某些点的距离，例如
a[i][j]指的是i号点到j号点的距离是a[i][j]秦大佬暂时退役了
QwQ
你是不是也是一个竞赛选手啊 ，感觉你也很强
秦同学大佬 这个既然是与floyd有关系 那么到哪个点不是最外层的循环
有关系,不代表很这类算法一模一样,他们有关系,是因为状压有一部分Floyd算法的思维.
同学用python怎么表示状态的变化呢？我尝试提前建立长度为2**n的二进制列表来表示状态，但这个创建时间太长了怎么办？
emm,我不会$python$,所以我也没有办法啊.
python直接有set类型
%%%
大佬我想问问为什么f[1][0]初始化为0，起点是0，那不应该是f[0][0]初始化为0吗
这里的$1$，是二进制下的$1$，也就是第$0$位为$1$，然后后面的$0$表示，上一次开始的点是$0$.
$f[i][j]$表示二进制状态为$i$，最后一次节点是$j$
谢谢，我把2的0次方当成0了
您客气了。
倒数第五行判断那里 我写成 if(i^(1<<j)&1) 这样也过了。。。。就没有判断第k位莫名其妙的就过了。。
emm，我有点懵逼，是数据太水了吗？
貌似 应该是吧
好像不是
我觉得在举个例子更好，我理解了好半天，推个例子直接出来了
好的
请问这和djikstra算法有什么不同？
dijskra是单源最短路径的算法,我们这个是基于Floyd算法,也就是多源最短路算法.
谢谢您
大佬，这个题目用递归，然后回溯法优化怎么写呢？我发你个代码帮我看看
好的.