题目描述
最短Hamilton路径,一个简单的路径打印方法
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 21, M = 1 << N;
int n;
int a[N][N];
int f[M][N], p[M][N];
int main()
{
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
cin >> a[i][j];
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
for (int i = 1; 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) {
int tmp = f[i - (1 << j)][k] + a[k][j];
if (f[i][j] > tmp) {
f[i][j] = tmp;
p[i][j] = k;
}
}
cout << f[(1 << n) - 1][n - 1] << endl;
// 打印方案
// int cur = n - 1, st = (1 << n) - 1;
// int tmp;
// while (n --) {
// cout << cur << ' ';
// tmp = p[st][cur];
// st -= 1 << cur;
// cur = tmp;
// }
return 0;
}