#837. 最短Hamilton路径

最短Hamilton路径

题目描述:

给定一张 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

提示