#4. 最短Hamilton路径
最短Hamilton路径
题目描述
给定 n 个点的带权无向图,求从0号点出发、恰好访问每个点一次、最终到达 n−1 号点的最短 Hamilton 路径。
输入格式
首行 n≤20,随后 n 行为 n×n 的边权矩阵。
输出格式
输出最短路径长度。
样例输入
4
0 2 1 3
2 0 2 1
1 2 0 1
3 1 1 0
样例输出
4
题意整理;原题与输入输出格式对照。
给定 n 个点的带权无向图,求从0号点出发、恰好访问每个点一次、最终到达 n−1 号点的最短 Hamilton 路径。
首行 n≤20,随后 n 行为 n×n 的边权矩阵。
输出最短路径长度。
4
0 2 1 3
2 0 2 1
1 2 0 1
3 1 1 0
4
题意整理;原题与输入输出格式对照。