数据范围： n ≤ 20 n\leq20 n≤20 题解：考虑两种状态，第一走了哪几个个点，第二是目前走到哪个点上面，然后用状态压缩进行DP，状态转移方程如下： f [ s t a t e ] [ j ] = m i n ( f [ s t a t e ] [ j ] , f [ s t a t e − j ] [ k ] + w [ k ] [ j ] ) f[state][j]=min(f[state][j],f[state-j][k]+w[k][j]) f[state][j]=min(f[state][j],f[state−j][k]+w[k][j]) 附上代码：
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int maxn=20+5; int n,w[maxn][maxn],f[1<<20][maxn]; int main() { 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; for(int i=1;i<(1<<n);i++){ for(int j=0;j<n;j++){ if(i>>j&1){ for(int k=0;k<n;k++){ if(i>>k&1){ f[i][j]=min(f[i][j],f[i^(1<<j)][k]+w[k][j]); } } } } } printf("%d\n",f[(1<<n)-1][n-1]); return 0; }