图片说明

我们可以先自然想到一个朴素的做法，就是直接通过枚举n个点所以的序列，然后求出每条路的权值和，最后取最小的即可。但是，我们看一下数据范围，发现如果这样算的话时间复杂度为n（n!）。所以我们要想一下用什么办法进行优化，我们发现，对于最多n个点的状态，我们可以用一个二进制进行表示，比如，我们遍历了1,3,4这三个点，那么他们的状态就是1011,去他对应的十进制进行存储即可，我们发现最大也就是2^20-1,这是可以接受的，时间复杂度为O(n^2*2^n)。我们可以用状态压缩的方法进行存储，比如，我们此时要求遍历到了第j个点的时候，对应的状态i的最小值，我们这里用f[i][j]进行表示，我们假设这中间的一个状态为tmp，那么，我们的结果就可以由f[i][j]=min(f[i][j],f[tmp][k]+a[k][j])得来。就是一个结果值我们可以由中间的某一个状态进行得来。这是一个很基本的状态压缩DP的思想。
代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[22][22];
int f[1<<20][20];
int main(){
    memset(f,0x3f3f3f3f,sizeof(f));
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    f[1][0]=0;
    for(int i=1;i<1<<n;i++){
        for(int j=0;j<n;j++){
            if(i>>j&1){  //判断这个状态i里面的第j位是否为1,为1才可以进行状态转移
                for(int k=0;k<n;k++){
                    if((i-(1<<j))>>k&1){  
//判断这个状态i减去j遍历的情况之后的第k个点是否被遍历，只有i的二进制里面的第j位和第k位都为1的时候我们才可以进行状态转移
                        f[i][j]=min(f[i][j],f[(i-(1<<j))][k]+a[k][j]);
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1][n-1]<<endl;
    return 0;
}