如图：求v1到v10的最短路径长度及最短路径。
1474: 最短路径
时间限制: 1 Sec 内存限制: 128 MB提交: 45 解决: 35
[提交][状态][讨论版]
题目描述
下图表示城市之间的交通路网(只能从编号小的城市到编号大的城市单向通行)，线段上的数字表示费用，单向通行由A->E。请求出A->E的最省费用。
如图：求v1到v10的最短路径长度及最短路径。
如图：求v1到v10的最短路径长度及最短路径。
输入
第一行，一个整数n，表示n个城市。（n<20）
接下为n行，分别代表该城市到其他城市的费用。
接下为n行，分别代表该城市到其他城市的费用。
输出
第一行为1号城市到n号城市的最短路径长度。
第二行为最短路径。
第二行为最短路径。
样例输入
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样例输出
minlong=19
1 3 5 8 10