题目描述

给定一张 lns="http://www.w3.org/1998/Math/MathML">�n 个点的带权无向图，点从 lns="http://www.w3.org/1998/Math/MathML">0∼�−10∼n−1 标号，求起点 lns="http://www.w3.org/1998/Math/MathML">00 到终点 lns="http://www.w3.org/1998/Math/MathML">�−1n−1 的最短 Hamilton 路径。Hamilton 路径的定义是从 lns="http://www.w3.org/1998/Math/MathML">00 到 lns="http://www.w3.org/1998/Math/MathML">�−1n−1 不重不漏地经过每个点恰好一次。`

输入格式

第一行输入整数 lns="http://www.w3.org/1998/Math/MathML">�n。 接下来 lns="http://www.w3.org/1998/Math/MathML">�n 行每行 lns="http://www.w3.org/1998/Math/MathML">�n 个整数，其中第 lns="http://www.w3.org/1998/Math/MathML">�i 行第 lns="http://www.w3.org/1998/Math/MathML">�j 个整数表示点 lns="http://www.w3.org/1998/Math/MathML">�i 到 lns="http://www.w3.org/1998/Math/MathML">�j 的距离（记为 lns="http://www.w3.org/1998/Math/MathML">�[�,�]a[i,j]）。 对于任意的 lns="http://www.w3.org/1998/Math/MathML">�,�,�x,y,z，数据保证 lns="http://www.w3.org/1998/Math/MathML">�[�,�]=0，�[�,�]=�[�,�]a[x,x]=0，a[x,y]=a[y,x] 并且 lns="http://www.w3.org/1998/Math/MathML">�[�,�]+�[�,�]≥�[�,�]a[x,y]+a[y,z]≥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