题目描述
给定一张 n
个点的带权无向图,点从 0∼n−1
标号,求起点 0
到终点 n−1
的最短 Hamilton 路径。
Hamilton 路径的定义是从 0
到 n−1
不重不漏地经过每个点恰好一次。
样例
#include<iostream>
#include<cstring>
using namespace std;
const int N = 20, M = 1 << N; // 定义常量N=20, M=2^N
int n; // 顶点数量
int w[N][N]; // 边的权重
int f[M][N]; // 动态规划数组
int main()
{
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数组为最大值,表示无穷大
f[1][0] = 0; // 初始条件
for(int i = 0; i < 1 << n; i++) // 枚举所有子集
for(int j = 0; j < n; j++) // 遍历顶点
if(i >> j & 1) // 当前顶点j在子集中
for(int k = 0; k < n; k++) // 遍历顶点
if(i - (1 << j) >> k & 1) // 子集中除j外包含顶点k
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]); // 动态规划递推
cout << f[(1 << n) - 1][n - 1]; // 输出最终结果
return 0;
}