百练4124 海贼王之伟大航路

航路"/>

百练4124 海贼王之伟大航路

传送门：百练4124 海贼王之伟大航路

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20;
int mp[maxn][maxn];
int dp[(1<<maxn)+10][maxn];int main(){int n;while(~scanf("%d",&n)){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&mp[i][j]);memset(dp,0x3f,sizeof(dp));dp[1][1]=0;  //以1为起点，到达这个点的最短路径为0int ans=(1<<n)-1;for(int k=1;k<=ans;k++){  //状态，k代表已走过节点的集合for(int i=1,_i=1;i<=n;i++,_i<<=1){ //到达的点if(k&_i==0) continue;for(int j=1,_j=1;j<=n;j++,_j<<=1){  //中间可能途径的点if(i==j||k&_j==0) continue;dp[k][i]=min(dp[k][i],dp[k^_i][j]+mp[j][i]);}}}printf("%d\n",dp[ans][n]);}return 0;
}