AcWing 731. 毕业旅行问题
原题链接
中等
作者:
春江花月夜ovo
,
2024-03-25 23:01:11
,
所有人可见
,
阅读 13
状压板子题
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef pair<int, int> PII;
const int N = 20, M = (1 << 20);
int dp[M][N];
int w[N][N];
int n;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
cin >> w[i][j];
memset(dp, 0x3f, sizeof dp);
dp[1][0] = 0;
for (int i = 1; i < 1 << n; i ++)
for (int j = 0; j < n; j ++)
for (int k = 0; k < n; k ++)
if (!(i & (1 << k)))
dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + w[j][k]);
int ans = 1 << 30;
for (int i = 1; i < n; i ++) ans = min(ans, dp[(1 << n) - 1][i] + w[i][0]);
cout << ans << "\n";
return 0;
}