DP
状态定义
dp[i][j]表示:如果i的二进制下该位是1,则表示该节点已经走过。并且当前处于j节点的最短路。
状态转移
dp[i][j] = min(dp[i ^ (1 << j)][k] + a[k][j])
表示当前处于j节点是由k节点走过来的。之所以要将i ^ (1 << j)是因为当前处于j节点,那么j节点之前是一定没有走到过的。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int a[25][25];
int f[1 << 21][25];
signed main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
memset(f, INF, sizeof f);
f[1][0] = 0;
for (int i = 1; i < 1<<n; i++) {
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
for (int k = 0; k < n; k++) {
if (i ^ (1 << j) & (1 << k)) {
f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + a[k][j]);
}
}
}
}
}
cout << f[(1 << n) - 1][n-1] << "\n";
}