快递员秋葵的烦恼

快递员秋葵的烦恼

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

萌新院程序设计能力检测Round1

未参加
状态
已结束
规则
OI
题目
3
开始于
2020-04-25 08:00
结束于
2020-04-25 12:00
持续时间
4.0 小时
主持人
参赛人数
5