问题 A: 最短路径
内存限制：128 MB
时间限制：1.000 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：155
通过：80
题目描述
下图表示城市之间的交通路网，线段上的数字表示路径长度，通行由A->E。试用动态规划的最优化原理求出A->E的最短路径。
输入格式
第一行输入一个整数，表示有几个城市。
后面的n行表示城市之间的通断情况；
后面的n行表示城市之间的通断情况；
输出格式
输出两行，第一行输出
minlong=一个整数（该整数为从第1个城市到第n个城市的最短路径值）
第一行输出最短路径，中间用空格隔开
minlong=一个整数（该整数为从第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