#4. 最短Hamilton路径
最短Hamilton路径
题目描述
给定一张 个点的带权无向图,点从 标号,求起点 到终点 的最短Hamilton路径。 Hamilton路径的定义是从 到 不重不漏地经过每个点恰好一次。
输入格式
第一行一个整数 。
接下来 nijij$ 的距离(一个不超过的正整数,记为 )。
对于任意的 ,数据保证 并且 。
输出格式
一个整数,表示最短Hamilton路径的长度。
样例
4
0 2 1 3
2 0 2 1
1 2 0 1
3 1 1 0
4
样例解释
从0到3的Hamilton路径有两条,0-1-2-3和0-2-1-3。前者的长度为2+2+1=5,后者的长度为1+2+1=4