AcWing 731. 毕业旅行问题
原题链接
中等
作者:
geats兔
,
2024-04-02 22:10:32
,
所有人可见
,
阅读 3
#include<iostream>
#include<cstring>
using namespace std;
const int N=20;
int n;
int w[N][N];
int f[1<<N][N];
int main(){
cin>>n;
memset(f,0x3f,sizeof f);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>w[i][j];
f[1][0]=0;
for(int i=0;i<1<<n;i++)
for(int j=1;j<n;j++)
if(i>>j&1){
for(int k=0;k<n;k++)
if(i-(1<<j)>>k&1){
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
}
}
int res=20000;
for(int i=0;i<n;i++) res=min(res,f[(1<<n)-1][i]+w[i][0]);
cout<<res<<endl;
return 0;
}