题目链接在这里:Lutece (uestc.edu.cn)
典型的状压dp,对于状压dp一般有三重循环,第一个枚举状态,第二个和第三个分别枚举一个状态到另一个状态的起点和终点。
#include "bits/stdc++.h"
using namespace std;
const int MAX=5e6+5;
int n;
int a[30][30];
int f[MAX][30];
int main(){
int i,j,k,ans=1e9;
cin>>n;
memset(f,0x3f,sizeof(f));
f[1][0]=0;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
cin>>a[i][j];
for (i=1;i<(1<<n-1);i++)
for (j=0;j<n-1;j++)
for (k=0;k<n-1;k++){
if (j==k) continue;
if ((i&(1<<k))==0 && (i&(1<<j))!=0){
f[i+(1<<k)][k]=min(f[i+(1<<k)][k],f[i][j]+a[j][k]);
}
}
ans=min(ans,f[(1<<n-1)-1][i]+a[i][n-1]);
cout<<ans;
return 0;
}
/*
3
0 5 8
5 0 3
8 3 0
*/