(状态压缩DP)
直接在走到最后一个位置的时候在看一下从这个位置到达北京的位置的最小值就行
91. 最短Hamilton路径
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1 << 20, M = 20;
int f[N][M];
int w[M][M];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
scanf("%d", &w[i][j]);
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for(int i = 0; i < 1 << n; i ++)
{
for(int j = 0; j < n; j ++)
{
if(i >> j & 1)
{
for(int k = 0; k < n; k ++)
{
if(((i - (1 << j)) >> k) & 1)
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}
}
}
}
int res = 0x3f3f3f;
for(int i = 0; i < n; i ++)
{
res = min(res, f[(1 << n) - 1][i] + w[i][0]);
}
cout << res;
}