问题 B: 城市交通网络图
内存限制：128 MB
时间限制：1 S
题面：传统
评测方式：文本比较
上传者：
提交：1849
通过：1382
题目描述
有 n 个城市，编号 1~n，有些城市之间有路相连，有些则没有，有路则会有一个距离。图 所示为一个含有 11 个城市的交通图，连线上的数（权）表示距离。
现在规定只能从编号小的城市到编号大的城市。问：从编号为 1 的城市到编号为n 的城市之间的最短距离是多少？
现在规定只能从编号小的城市到编号大的城市。问：从编号为 1 的城市到编号为n 的城市之间的最短距离是多少？
输入格式
【输入格式】
第 1 行为 n，表示城市数，n≤100。
下面的 n 行是一个 n×n 的数组map[i,j]，其中 map[i,j]=0 表示城市 i和城市 j 之间没有路相连，否则为两者之间的距离。
第 1 行为 n，表示城市数，n≤100。
下面的 n 行是一个 n×n 的数组map[i,j]，其中 map[i,j]=0 表示城市 i和城市 j 之间没有路相连，否则为两者之间的距离。
输出格式
【输出格式】
一行一个数，表示最短距离。数据保证一定可以从城市 1 到城市 n。
一行一个数，表示最短距离。数据保证一定可以从城市 1 到城市 n。
输入样例 复制
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输出样例 复制
13