问题 F: Lh的约会

问题 F: Lh的约会

时间限制: 1 Sec  内存限制: 128 MB
提交: 296  解决: 70
[状态] [讨论版] [提交] [命题人:]
题目描述

    有n个城市,编号为1~n,有些城市之间有路相连,有些没有。Lh在城市1,要去跟在城市n的女朋友约会,Lh想尽快见到女朋友,所以不想走太多的路,但是Lh有一个习惯就是只从编号小的城市到编号大的城市,问Lh要走的路最短距离是多少。

注意:
    若Lh一开始就和其女朋友在一个城市,那么Lh显然就不需要再长途跋涉的对吧。

输入

输入的第一行包含一个正整数TT<=20),表示一共有T组数据.

每组数据先输入一个n,表示城市个数,1<=n<=100;

接着有n行,没行有n个数。第一行表示第一个城市跟n个城市之间的道路情况。

map[i,j]=0,表示城市ij之间没有路,否则就是ij之间道路的距离。0<=map[i][j]<=100;数据保证有答案。

输出

一个正整数表示Lh1n要走的最短的距离。答案占一行。

样例输入 Copy
1
11
0 5 3 0 0 0 0 0 0 0 0
5 0 0 1 5 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
样例输出 Copy
13