题目描述
给定一张 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≤n≤20
0≤a[i,j]≤107
样例
输入样例：
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
状态压缩DP分析:
1.本题思路
假设:一共有七个点,用0,1,2,3,4,5,6来表示,那么先假设终点就是5,在这里我们再假设还没有走到5这个点,且走到的终点是4,那么有以下六种情况:
first: 0–>1–>2–>3–>4 距离:21
second: 0–>1–>3–>2–>4 距离:23
third: 0–>2–>1–>3–>4 距离:17
fourth: 0–>2–>3–>1–>4 距离:20
fifth: 0–>3–>1–>2–>4 距离:15
sixth: 0–>3–>2–>1–>4 距离:18
如果此时你是一个商人你会走怎样的路径?显而易见,会走第五种情况对吧?因为每段路程的终点都是4,且每种方案的可供选择的点是0~4,而商人寻求的是走到5这个点的最短距离,而4到5的走法只有一种,所以我们选择第五种方案，可寻找到走到5这个点儿之前,且终点是4的方案的最短距离,此时0~5的最短距离为(15+4走到5的距离).(假设4–>5=8)
同理:假设还没有走到5这个点儿,且走到的终点是3,那么有一下六种情况:
first: 0–>1–>2–>4–>3 距离:27
second: 0–>1–>4–>2–>3 距离:22
third: 0–>2–>1–>4–>3 距离:19
fourth: 0–>2–>4–>1–>3 距离:24
fifth: 0–>4–>1–>2–>3 距离:26
sixth: 0–>4–>2–>1–>3 距离:17
此时我们可以果断的做出决定:走第六种方案!!!,而此时0~5的最短距离为(17+3走到5的距离)(假设3–>5=5)
在以上两大类情况之后我们可以得出当走到5时:
1.以4为终点的情况的最短距离是:15+8=23;
2.以3为终点的情况的最短距离是:17+5=22;
经过深思熟虑之后,商人决定走以3为终点的最短距离,此时更新最短距离为:22。
当然以此类推还会有以1为终点和以2为终点的情况,此时我们可以进行以上操作不断更新到5这个点的最短距离,最终可以得到走到5这个点儿的最短距离,然后再返回最初的假设,再依次假设1,2,3,4是终点,最后再不断更新,最终可以得出我们想要的答案
2.DP分析:
用二进制来表示要走的所以情况的路径,这里用i来代替
例如走0,1,2,4这三个点,则表示为:10111;
走0,2,3这三个点:1101;
状态表示:f[i][j];
集合:所有从0走到j,走过的所有点的情况是i的所有路径
属性:MIN
状态计算:如1中分析一致,0–>·····–>k–>j中k的所有情况
状态转移方程:f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j])
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20,M=1<<N;
int f[M][N],w[N][N];//w表示的是无权图
int main()
{
int n;
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;//因为零是起点,所以f[1][0]=0;
for(int i=0;i<1<<n;i++)//i表示所有的情况
for(int j=0;j<n;j++)//j表示走到哪一个点
if(i>>j&1)
for(int k=0;k<n;k++)//k表示走到j这个点之前,以k为终点的最短距离
if(i>>k&1)
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);//更新最短距离
cout<<f[(1<<n)-1][n-1]<<endl;//表示所有点都走过了,且终点是n-1的最短距离
//位运算的优先级低于'+'-'所以有必要的情况下要打括号
return 0;
}
大佬这题解写的 tql
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
不要给我发绿尸寒啊，丁真珍珠先生
怎么在哪里都能看到芝士丁真
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴，来口瑞克五>.<
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
/眼（00）丁真，鉴定为：%
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
$ 雪豹闭嘴 $
闭嘴雪豹
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
纪念，打卡 ， ✌语言丁真，鉴定为c++
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
？？？什么梗
看楼主头像
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
雪豹闭嘴
丁真 哥哥
雪豹请闭嘴
雪豹闭嘴
雪豹闭嘴
说一个细节的我的理解，由于状态从0到1<<n,是从小到大遍历的，求这个状态最值的过程中，用到的都是把某一位1变成0的状态，而把1变成0之后这个二进制数一定会变小，那么它就一定是算好的（因为从小往大遍历的每个状态）
同学们加油
哈哈哈，好多好多冒充y总的
请问为什么, 先循环状态, 再循环所有点
你要先算出来这个状态的所有落脚点的值,再算下个状态的值
为啥要算完所有状态呀
计算出 0 到 2^n - 1 递增的状态上不同终点与路径的最小值，后面状态的计算需要用到前面状态的结果
为什么当k大于j还能算呢
比如一个二进制11111111，他中间有很多个1，但是他不一定是从0到1再到2再到3最后到n-1这个点，他里面的顺序可以是打乱的
懂啦，谢谢解释
搞不懂为什么第一个题，初始化为零，这个题初始化为正无穷
因为这题是求最小值
好的
请问，状态转移的时候，k是可以等于j的吗？ 感觉很奇怪。
不能，但是转移也不影响结果 如果k=j 那么从k转移到j 等于自己到自己 w[k][j] = 0
f[i][j] = min(f[i][j], f[i - (1 << j)][j] + w[k][j]; 那么如果当k == j的话, f[i][j] = min(f[i][j], f[i - (1 << j][j] + 0; 这里的i - (1 << j) 不包含j点,它就没有经过j点,那这样不会产生混乱吗？
兄弟你这个状态方程写错了哦f[i - (1 << j)][k]这个二维的地方是k不是j
在这里可以j，这种情况下，dp[i-(1<<j)][j]是一开始设定的极大值，因为这个点在之前的循环中没有被修改过
当k==j时，转移方程变为f[i][j] = min(f[i][j], f[i - (1 << j)][j] + w[j][j])，因为f[i - (1 << j)][j]是不合定义的状态，因此仍然是初始最大值，而w[j][j]值为0，因此加和仍为初始最大值，在min函数执行时不会造成任何影响(相当于跳过了）。
其实加入if(k == j) continue;可以得出依旧是可以ac的，因此效果和跳过一样
不可以，但是你可以找个例子代入看一看，然后就会发现k=j时根本不会参与运算自己也不会被运算为别的数
# 好牛逼
## 谢谢大佬
tql我竟然懂了
6
大佬, 请问最后的答案为什么是f[(1<<n)-1][n-1]
1<<n 是二进制表示首位是1后面都是0, 比如 1<<2 的二进制表示是 100
这样 f[(1<<n)-1][n-1] 表示的是 最后走到 n-1 个点, 走过的点的状态是 100000… (等于只走了第n-1个点)
我理解, 正确的答案应该是 最后走到n-1个点, 走过的点的状态是 11111… 这种状态才对,
你倒数第二行说错了， f[(1<<n)-1][n-1] 表示的是最后走到n-1 个点，走过的点的状态就是1111.....11（一共n个1）；因为1 <<n 等于1后面n个零，你再减去1不就是一共n个1了
牛逼！位运算太妙了，减去二进制的1，就是最高位为0，低位全1，恰好就是从0走到n-1的状态！
就我异或这题为什么不能用图的算法解决吗
我也是这题一看应该是最短路啊
tle啊，你说为什么叫状压（以空间换时间）
朴素O（n!）规模最大是n=10
最短Hamilton路径是要求每个点都走到而且距离最短，但是最短路不一定走过了每个点
想知道，为什么最后的结果就是f[(1<<n)-1][n-1],为什么最小的路径一定是以n-1这个点结尾呢，有大佬能指点一下吗
这个是题目要求的啊,n-1就是终点
哦哦，没注意，以为是找到一个任意的汉密尔顿环路的最小值，谢谢
这为什么就状态压缩了呢，不太明白状态压缩什么意思
将路径的状态用二进制压缩
一直搞不懂状态压缩是什么意思……
就是用二进制数来表示状态，比如说0001代表整数1，就代表走过了1这个点。
大概是明白了，看来得多刷几次
for里面加的两个if有什么用
表示这个点可以走到
谢谢
是如何保证一定从起点0出发的呢？
题目有说的
我想问的是代码如何保证是从0出发的
因为他的初始状态是0已经经过的状态
哦哦好的好的，感谢感谢，%%%
不用谢
兄弟，我这里还没太明白，可以帮忙讲解一下吗，为啥能保证起点0出发的呢
老师，您好，请教一下呢，为什么f[1][0]=0就能保证是从0出发的呢，那我写f[0][0]=0或者f[2][0]=0可不可以保证是从0出发的呢
你没理解f[1][0]的含义，前一个数表示状态，1的二进制表示为00…0001,二进制每位表示有没走过，此时0的位置上为1就表示走过了，且0到0距离最小值为0，所以这样初始化，视频讲的很清楚了你可以再看看
请问一下，后面如果更新状态时候是从0更新的，比如f[111][2]是从f[011][0]更新过来的，会不会导致最后的哈密顿图不是从0开始呢
枚举的前一个状态已经被算过是因为 [ i-(1<<j ] 这个状态比 [ i ] 小，而 i 是从小到大枚举的，是这样吗？
对,这里是二进制的特殊性,当我们对任何一个是1的位操作时,我们必然已经枚举它之前的所有状态
first: 0–>1–>2–>3–>4 距离:21。这个距离是怎么算的呀，题目意思给我看蒙了。
这个不是算的，这个是我假设的
这个就是根据样例算出来的，楼主时间长了也忘了估计
题目意思就是第一个行第一列表示0到0点距离，第一行第二列表示0到1的距离，后面就是表示0到2的距离
我刚刚推半天推不对我还一直以为我题意理解错了
哈哈哈哈
我也推半天呢，无奈把题解丢给chat-gpt，gpt按照题解的推理也对不上，看到这条评论我心情只有…
这句话是什么意思啊 大佬
i的第j位为1，意思就是点j在状态i里这个应该是判断i的j+1位是否为1吧
意思就是枚举状态 i 中所有路径经过 j 点的 j
很详细O~一下子就懂了~
# 谢谢大佬！学到了很多~
# 涨姿势了
走0124三个点为什么是11101，023为什么又是1101？