交通问题例题P476 增加路径输出 - Problem

Problem B: 交通问题例题P476 增加路径输出

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 128 MiB

Submit ProblemList Solved: 24 Submit Num: 55 Statistics ShowOff!

Description

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

如图：求v1到v10的最短路径长度及最短路径。

Input

第一行n。表示矩阵大小。 n<=100。
接下来n行n列的数aij表示第i个城市到第j个城市是否连接。不连接用0表示，连接就用一个整数表示他们的距离。 0<=aij<=100。

Output

第一行表示最短距离。
第二行表示经过的城市路径。

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

19
1 3 5 8 10

HINT

---
acg
yzs 32512

Submit