AcWing 91. 最短Hamilton路径
原题链接
中等
作者:
Snrise
,
2024-04-06 17:11:37
,
所有人可见
,
阅读 1
f[i][j]表示路过i的二进制表示中为1的这些点从0号点到达j号点最短距离;
f[有j][j] = min(f[有j][j],f[无j有k][k]+w[k][j]);
#pragma GCC optimize(3)
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 20;
const int M = 1 << N;
int f[M][N];
int w[N][N];
int n;
signed main(void)
{
std::ios::sync_with_stdio(false);
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号点必定在集合中,所以可以优化成i+=2;
for (int i = 3; i < 1 << n; i += 2)
{
for (int j = 0; j < n; j++)
{
if (i >> j & 1)
{
for (int k = 0; k < n; k++)
{
int u = i - (1 << j);
if (u >> k & 1)
{
f[i][j] = min(f[i][j], f[u][k] + w[k][j]);
}
}
}
}
}
cout << f[(1 << n) - 1][n - 1] << endl;
return 0;
}