本题解采用 $\text{C++}$ 版本进行讲解。

题目描述

给定一张 $n$ 个点的带权无向图，点从 $0∼n−1$ 标号，求起点 $0$ 到终点 $n−1$ 的最短 $\text{Hamilton}$ 路径。

$\text{Hamilton}$ 路径的定义是从 $0$ 到 $n−1$ 不重不漏地经过每个点恰好一次。

样例

Input:
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
Output:
18

算法1

我们发现 $n=20$ ，范围并不大，可以采用枚举 $n$ 个点的全排列的方法，然后计算路径长度的最小值。

具体地，我们使用 $\text{next_permutation}$ 生成排列，每次再根据生成顺序进行统计。

如果你不了解 $\text{next_permutation}$ 怎么用，这里有一个示例：

#include<bits/stdc++.h>
using namespace std;
int a[6];
int times=0;
int main(){
    a[1]=5;
    a[2]=2;
    a[3]=6;
    a[4]=1;
    a[5]=7;
    do{
        ++times;
        for(int i=1;i<=5;i++)
        cout<<a[i]<<" ";
        cout<<endl;
    } while(next_permutation(a+1,a+6));
    cout<<times<<endl;
    sort(a+1,a+6);
    times=0;
    do{
        ++times;
        for(int i=1;i<=5;i++)
        cout<<a[i]<<" ";
        cout<<endl;
    } while(next_permutation(a+1,a+6));
    cout<<times<<endl;  
    return 0;
}

经过观察可以发现，在使用 $\text{next_permutation}$ 之前，一定要对原数组排序，否则最后枚举数会比应有的枚举数要少。这里不再详细介绍。

然后是这一部分的代码：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll n;
#define N 20
ll a[N][N];
ll b[N];
void readin(){
    cin>>n;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    for(ll i=0;i<n;i++)
    b[i]=i;
}
void calculate(){
    ll mincost=INF;
    do{
        ll cost=0;
        if(b[0]==0&&b[n-1]==n-1){
            for(ll j=0;j<n-1;j++){
                cost+=a[b[j]][b[j+1]];
            }
        mincost=min(mincost,cost);}
    } while(next_permutation(b,b+n));
    cout<<mincost<<endl;
}
int main(){
    readin();
    calculate();
    return 0;
}

恭喜你，得分 $\text{40pts}$ 。很明显，这样的算法会超时。

算法2

看到数据范围，不难想到状压 $\text{dp}$。
下面为了叙述方便，定义：在 $m$ 位二进制中，称最低位为 $0$ 位，从右到左依此类推，最高位则为 $m-1$ 位。
定义 $dp[i][j]$ 代表当目前状态为 $i$ ，且处于第 $j$ 个点时的最小价值。
什么是“状态”？就比如，一共有 $5$ 个点，编号 $0~4$ ，你已经经过了点 $0,1,3$ ，此时你的状态就是 01011。
也就是说，你的状态是一个 $n$ 为二进制数，其中第 $i$ 为若为 $1$ ，则代表你已经经过这个点；反之，则代表你没有经过这个点。

对于初始化，就是当 $i=1,j=0$ 时，此时位于起点，最短路为 $0$ 。其余均为 INF。

对于目标，就是 dp[(1<<n)-1][n-1]

对于 dp[i][j] ，注意到此时 $j$ 点一定是刚刚到达，所以上一步对应的二进制数的第 $j$ 位一定为 $0$。所以，我们只需再枚举上一次经过的点 $k$，满足在 i xor (1<<j) 中的第 $k$ 位为 $1$ ，即可转移。

大致思路如上，具体细节请参考代码。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll n;
#define N 20
ll a[N][N];
ll dp[1<<N][N];
void readin(){
    cin>>n;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
}
void calculate(){
    //dp[i][j] 代表在状态为 i 的情况下目前处于点 j 时的最短路径
    memset(dp,INF,sizeof(dp));
    dp[1][0]=0;
    for(ll i=1;i<(1<<n);++i){
        for(ll j=0;j<n;++j){
            if((i>>j)&1){
                //合理
                ll f0=(i xor (1<<j));
                for(ll k=0;k<n;++k){
                    if((f0>>k)&1){
                        dp[i][j]=min(dp[i][j],dp[f0][k]+a[k][j]);
                    }
                } 
            }
        }
    }   
    cout<<dp[(1<<n)-1][n-1]<<endl;
}
int main(){
    readin();
    calculate();
    return 0;
}

时间复杂度 $0(2^n\times n^2)$