AcWing 91. 最短Hamilton路径
原题链接
中等
作者:
自律
,
2021-08-30 16:04:40
,
所有人可见
,
阅读 178
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20,M = 1 << N;
int w[N][N];
int f[M][N];
int main()
{
int n;
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 = 0;i < 1 << n;i ++)
for(int j = 0;j < n;j ++)
if(i >> j & 1) //保证i表示的状态下包含j
for(int k = 0;k < n;k ++)
if(i - (1 << j) >> k & 1) //保证i表示的状态下去除j之后包含k
f[i][j] = min(f[i][j],f[i - (1 << j)][k] + w[k][j]);
cout<<f[(1 << n) - 1][n - 1]<<endl; //位运算的优先级低于'-'
return 0;
}