#E. 最短 Hamilton 路径

    Type: Default 1000ms 256MiB

最短 Hamilton 路径

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一张 nn 个点的带权无向图,点从 0n10 \sim n-1 标号,求起点 00 到终点 n1n-1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 00n1n-1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 nn

接下来 nn 行每行 nn 个整数,其中第 ii 行第 jj 个整数表示点 iijj 的距离(记为 a[i,j]a[i,j])。

对于任意的 x,y,zx,y,z,数据保证 a[x,x]=0a[x,y]=a[y,x]a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]a[x,z]a[x,y]+a[y,z] \ge a[x,z]

输出格式

输出一个整数,表示最短 Hamilton 路径的长度。

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
18
4
0 2 1 3
2 0 2 1
1 2 0 1
3 1 1 0
4

提示

对于所有测试数据满足 1n201 \le n \le 200a[i,j]1070 \le a[i,j] \le 10^7

位运算

Not Claimed
Status
Done
Problem
5
Open Since
2024-7-14 0:00
Deadline
2024-7-23 23:59
Extension
24 hour(s)