#P10447. 最短 Hamilton 路径

最短 Hamilton 路径

题目描述

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

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

输入格式

第一行输入整数 nn

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

对于任意的 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

提示

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