城市交通

2013年11月21日1,2240

题目描述

有n个城市,编号1~n,有些城市之间有路相连,有些则没有,有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市,问你从编号为1的城市走到编号为n的城市要花费的最短距离是多少?

输入

输入格式:
先输入一个n,表示城市数,n<100。
下面的n行,是一个n*n的邻接矩阵map[1..n,1..n]。
map[i,j]=0,表示城市i和城市j之间没有路相连,否则为两者之间的距离。

输出

输出格式:
一个数,表示从城市1走到城市n的最短距离。
输入数据保证可以从城市1走到城市n。

样例输入

6 0 1 4 1 0 0 1 0 2 0 4 0 4 2 0 0 0 3 1 0 0 0 3 2 0 4 0 3 0 2 0 0 3 2 2 0

样例输出

3

代码