题目描述

给定一张 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

算法1

当时学这个的时候也是比较迷，不太理解y总说的什么意思，后来参考了灰之魔女的题解和秦大佬的题解，再考虑了40多分钟终于觉得有所感悟，于是写了一篇题解。

这里特别感谢‘灰之魔女’大佬，几乎我看题解的时候，只要看见有她的，我总是第一个就点击她的，有的题解写的真的很棒。

代码中的理解难免有不妥之处，欢迎指证。

大体思路是y总的思路，代码参考了灰之魔女大佬的代码，有小处改动。

状态表示f[i][j]我想了好几种说法，每种都不太满意，最后找到一个综合的说法。

f[i][j]表示所有从0号点走到j号点，第i种情况下的路径之和。

把握住这个含义看代码的时候就比较好理解了

建议可以结合灰之魔女大佬的题解看，她在前面对基础部分做了很详细的解释。

本篇题解参考灰之魔女大佬题解和秦大佬的题解

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N=21,M=1<<N;//为什么这里定义1<<N呢？后面代码处会有解释，不能定义N过大，这样会编译错误
//我理解的是占用内存过大，空间复杂度过大。

int f[M][N],w[N][N];//f记录距离的总和例如f[2][4]表示第两种情况，从0号点到4号点的距离总和。
//w用来存储点与点之间的距离权重

int n;//n表示总共多少个点

int main()
{
    cin>>n;//n的数据较小可以使用cin，数据较大的时候建议使用scanf;

    for(int i=0;i<n;i++)//这里读取点与点之间的距离权重
        for(int j=0;j<n;j++)
            scanf("%d",&w[i][j]);//如i=0,j=4表示0号点到4号点的距离为1

    memset(f,0x3f,sizeof f);////因为要求最小值，所以初始化为每种情况的路径之和为无穷大

    f[1][0]=0;//第一种情况从0号点开始走到0号点，距离之和肯定为0啊！

    for(int i=1;i<1<<n;i++)//这里1<<n,表示i的所有情况，从数学上的排列组合考虑
    //i代表着是一个方案集合，其中每一个位置1和0，代表着这个点经过还是没有经过
    //这里我以n=5为例子来说明，n=5表示总共五个点，每个点都有两种情况，1和0，即代表要么经过要么没有经过
    //那么每个点都有两种可能，总共五个点，所有可能就是2*2*2*2*2=32；
    //1<<5=32,所以我们可以发现1<<5其实就是2^5的等价，这样也提高了代码的运行效率
    //这里i从1开始，当然从0开始也算对，因为从0开始遇到第一个if自动切换为i=1。
    //从1开始的实际意思是，第一种走的情况。
        for(int j=0;j<n;j++)//j表示走哪个点
            if(i>>j&1) //如果i集合中第j位是1，也就是到达这个点
            //举个例子，i=1，j=0，1>>0&1=1表示第一种情况，从0号点开始走到0号点。
            for(int k=0;k<n;k++) //k表示走到j这个点之前,以k为终点的最短距离
                if(i>>k&1) //确保i能到达k这个点
                    f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);//更新最短距离
                    //i-(1<<j)我的理解可能不太对，仅供参考
                    //因为我们首先要到j前面的k这个点，i代表的所有情况，1<<j代表已经到j的情况
                    //两个做差表示，i到k这个点的某一情况。

    cout<<f[(1<<n)-1][n-1]<<endl;//表示所有点都走过了,且终点是n-1的最短距离
    //为什么是(1<<n)-1,我理解的是排除0 0 0 0 0这种情况，即哪个点都不经过
    //位运算的优先级低于'+'-'所以有必要的情况下要打括号

    return 0;
}