AcWing 91. 最短Hamilton路径
原题链接
中等
作者:
Andy2035
,
2024-04-20 22:47:37
,
所有人可见
,
阅读 1
状压dp
#include<bits/stdc++.h>
using namespace std;
const int N = 21,M = (1 << N) + 1;
int f[N][M];
int n;
int a[N][N];
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)scanf("%d",&a[i][j]);
memset(f,0x3f,sizeof f);
f[0][1] = 0;
for(int i = 0;i<(1<<n);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)
f[j][i] = min(f[j][i],f[k][i - (1 << j)] + a[k][j]);
printf("%d\n",f[n-1][(1<<n) - 1]);
}