Problem1158--最短路径

1158: 最短路径

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 19  Solved: 16
[Submit] [Status] [Web Board] [Creator:]

Description

有多个城市组成了一个城市交通网，现给出一个城市交通网，要求计算出从起点1到终点n的最短路径。

Input

第一行输入一个数n，表示共有n个城市
接下来是n行n列的数据，表示从一个城市到另一个城市的距离，0表示两个城市不连通。

Output

输出两行，
第一行表示最短距离，用minlong表示，
第二行表示最短路径的城市，每个城市之间用空格分开。

Sample Input Copy 

10
0  2  5  1  0  0  0  0  0  0
0  0  0  0 12 14  0  0  0  0
0  0  0  0  6 10  4  0  0  0
0  0  0  0 13 12 11  0  0  0
0  0  0  0  0  0  0  3  9  0
0  0  0  0  0  0  0  6  5  0
0  0  0  0  0  0  0  0 10  0
0  0  0  0  0  0  0  0  0  5
0  0  0  0  0  0  0  0  0  2
0  0  0  0  0  0  0  0  0  0

Sample Output Copy 

minlong=19
1 3 5 8 10

Source/Category

dp 
[Submit] [Status]