#include <bits/stdc++.h> using namespace std; using ll = long long ; const int N=20,M=1<<N; ll dp[M][N+10],a[22][22]; int main() { ios::sync_with_stdio(false); 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=1;i<=(1<<n)-1;i++){ for(int j=0;j<=n;j++){ if(i>>j&1){ for(int k=0;k<n;k++){ if(i-(1<<j)>>k&1){ dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+a[k][j]); } } } } } cout<<dp[(1<<n)-1][n-1]; }
原文:https://www.cnblogs.com/qq1415584788/p/14835972.html