6087 - 例9.5 最短路径

通过次数

0

提交次数

0

时间限制 : 1 秒
内存限制 : 128 MB

图9-4表示城市之间的交通路网,线段上的数字表示费用,单向通行由A->E.试用动态规划的最优化原理求出A->E的最省费用。

1567842355539.png

输入

 

输出

 

样例

输入

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 

来源

一本通增补1