快递员秋葵的烦恼
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
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