Login Register

Problem A: 最短路径

Time Limit: 1 Sec Memory Limit: 128 MB
Submit Solution

Description

下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。
image.png

Input

第一行一个正整数n，表示有n个点。
接下来n*n的矩阵，表示点与点之间的距离。



Output

第一行：输出最短路径的值


Sample Input

10
0  2  5  1  0  0  0  0  0  0
0  0  0  0 12 14  0  0  0  0
0  0  0  0  6 10  4  0  0  0
0  0  0  0 13 12 11  0  0  0
0  0  0  0  0  0  0  3  9  0
0  0  0  0  0  0  0  6  5  0
0  0  0  0  0  0  0  0 10  0
0  0  0  0  0  0  0  0  0  5
0  0  0  0  0  0  0  0  0  2
0  0  0  0  0  0  0  0  0  0

Sample Output

minlong=19

HINT

n<=20, 距离的值均为小于100的非负整数数