UOJ Logo 小司码 Online Judge

XSMOJ

第280题   城市交通

Statistics

题目描述

​有 n 个城市,编号 1~n,有些城市之间有路相连,有些则没有,有路则会有一个距离。图 9.12-1 所示为一个含有 11 个城市的交通图,连线上的数(权)表示距离

现在规定只能从编号小的城市到编号大的城市。问:从编号为 1 的城市到编号为n 的城市之间的最短距离是多少?

输入格式

第 1 行为 n,表示城市数,n≤100。 下面的 n 行是一个 n×n 的邻接矩阵map[i,j],其中 map[i,j]=0 表示城市 i和城市 j 之间没有路相连,否则为两者之间的距离。

输出格式

一行一个数,表示1到n最小的距离。

样例数据

input


11
0 5 3 0 0 0 0 0 0 0 0
5 0 0 1 6 3 0 0 0 0 0
3 0 0 0 8 0 4 0 0 0 0
0 1 0 0 0 0 0 5 6 0 0
0 6 8 0 0 0 0 5 0 0 0
0 3 0 0 0 0 0 0 0 8 0
0 0 4 0 0 0 0 0 0 3 0
0 0 0 5 5 0 0 0 0 0 3
0 0 0 6 0 0 0 0 0 0 4
0 0 0 0 0 8 3 0 0 0 3
0 0 0 0 0 0 0 3 4 3 0

output


13

数据规模与约定

时间限制:$1 \text{s}$

空间限制:$64 \text{MB}$