快递员秋葵的烦恼

快递员秋葵的烦恼

测试数据来自 mengxinyuan/1003

Description

杜王町为了使居民串门方便进行了新一轮的城镇规划,在新一轮规划之后每两户都存在一条路径。而秋葵是杜王町的一个邮递员,每一天都要给每户送信,而每户所收的信为一封,秋葵如何送信才能使得所经过的路径最短呢?

Input

第一行输入一个整数n。
接下来n个整数,其中第i行第j个整数表示点i到点j的距离(记为a[i,j])。
对于任意的x,y,z,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

Output

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

Format

1≤n≤20
0≤a[i,j]≤10^7
(1s/64mb)

Input Example

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

Output Example

18

信息

ID
1002
难度
9
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者

相关

在下列训练计划中:

MAXの算法小讲堂= ̄ω ̄=