OI题库

【问题描述】

    X城有一个含有N个节点的通信网络，在通信中，我们往往关心信息从一个节点I传输到节点J的最短路径。遗憾的是，由于种种原因，线路中总有一些节点会出故障，因此在传输中要避开故障节点。
任务一：在己知故障节点的情况下，求避开这些故障节点，从节点I到节点J的最短路径S0。
任务二：在不考虑故障节点的情况下，求从节点I到节点J的最短路径S1、第二最短路径S2。

【输入文件】

第1行： N I J (节点个数 起始节点 目标节点)
第2—N+1行： Sk1 Sk2…SkN (节点K到节点J的距离为SkJ K=1，2，……，N)
最后一行： P T1 T2……Tp (故障节点的个数及编号)

【输出文件】

S0 S1 S2 (S1<=S2 从节点I到节点J至少有两条不同路径)

【输入输出样例】

route.in

5 1 5
0 10 5 0 0
10 0 0 6 20
5 0 0 30 35
0 6 30 0 6
0 20 35 6 0
1 2

route.out

40 22 30

【约束条件】

(1)N<=50 N个节点的编号为1，2，…，N
(2)Skj为整数，Skj<=100，(K，J=1，2…，N 若Skj=0表示节点K到节点J没线路)
(3)P<=5