AcWing 91. 最短Hamilton路径
原题链接
中等
作者:
ober02
,
2024-04-07 10:03:48
,
所有人可见
,
阅读 1
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20, M = 1 << N;
int f[M][N], w[N][N];
int n;
int main()
{
cin >> n;
for(int i = 0 ; i < n ;i++)
for(int j = 0 ; j < n; j++) cin >> w[i][j];
memset(f, 0x3f, sizeof f); // 初始化为正无穷
f[1][0] = 0; //从0点开始
for(int i = 1; i < 1<<n; i+=2){ //遍历所有的状态,1~2^n-1
for(int j = 1; j < n ;j++){//遍历所有要去的点
if(i >> j & 1){//状态中存在j点
for(int k = 0; k < n ;k++){//理论上遍历所有i中除j点以外所有的点k
if(i >> k & 1){
f[i][j] = min(f[i][j], f[i - (1<<j)][k] + w[k][j]);
}
}
}
}
}
cout << f[(1<<n) - 1][n-1];
return 0;
}