22. [HAOI 2005]路由选择问题

【题目描述】

任务一：在己知故障节点的情况下，求避开这些故障节点，从节点 $I$ 到节点 $J$ 的最短路径 $S_0$。
任务二：在不考虑故障节点的情况下，求从节点 $I$ 到节点 $J$ 的最短路径$S_1$、第二最短路径$S_2$。

所求路径均为简单路径：路径上的各顶点互不重复。

【输入格式】

第 $1$ 行： $N$ $I$ $J$ (分别表示节点个数、起始节点和目标节点)

第$2 \sim N+1$行： $S_{k_1}$ $S_{k_2}…S_{k_N}$

(表示节点 $K$ 到节点 $J$ 的距离为整数 $S_{k_J}$,若 $S_{k_j}=0$ 表示节点 $K$ 到节点 $J$ 没线路， $K=1，2，……，N$)

最后一行： $P$ $T_1$ $T_2$……$T_p$ (表示故障节点的个数及编号)

【输出格式】

$S_0$ $S_1$ $S_2$ ($S_1 \leq S_2$ 从节点 $I$ 到节点 $J$ 至少有两条不同路径)

【样例输入】

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

 

【样例输出】

40 22 30

【数据规模与约定】

对于 $100\%$ 的数据，$N \leq 50 ，S_{k_j} \leq 100 ，P \leq 5$。