陈远龙精品编程（信奥赛） 助力信奥赛学子取得优秀的成绩

题目描述

有n个城市，编号1 - n，有些城市之间有路相连，有些则没有，有路则会有一个距离，下图为一个含有11个城市的交通图，连线上的数（权）表示距离。

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

输入格式

第1行，一个正整数n，代表城市的个数

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

输出格式

1行，1个数，表示最短距离。数据保证一定可以从城市1到城市n。

样例 #1 输入

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

样例 #1 输出

13

数据范围与提示

100%的数据：$n \le 100$

测试点数目

共5个测试点，每个测试点20分

时间与内存限制

每个测试点时间：1000ms（1.0s），内存：256MiB

输入输出模式

本OJ支持两种输入输出模式