其实这玩意就是旅行商问题板子，没多大差别

题目要求0-n-1都必须经过，所以和TSP没差别

话说这个题怎么还卡我long long

题目链接

dp[i][j]表示当前经过节点的状态，j表示目前经过的最后一个节点

状态转移方程

$$dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j]+a[j][k])$$

#include<bits/stdc++.h>
using namespace std;
//#define int long long加了会爆内存re
const int N = 20;
int a[N][N];
int dp[1<<N][N];
signed main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            cin>>a[i][j];
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[1][0]=0;
    for(int i=0;i<(1<<n);i++) {
        for(int j=0;j<n;j++) {
            if (!(i&(1<<j))) {
                continue;
            }
            for(int k=0;k<n;k++) {
                if(i&(1<<k)) {
                    continue;
                }
                dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j]+a[j][k]);
            }
        }
    }
    cout<<(dp[(1<<n)-1][n-1])<<'\n';
}

这里提前continue了两个，所以复杂度不会爆

其实TSP问题的dp方程有很多种写法，不一定是这种，但是思路基本上都是一样的