OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HAOI2005】路由选择问题

【题目描述】

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至少有两条不同路径)

【输入样例】

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

【数据范围】

(1)N<=50 N个节点的编号为1,2,…,N

(2)Skj为整数,Skj<=100,(K,J=1,2…,N 若Skj=0表示节点K到节点J没线路)

(3)P<=5

【题解】

Task1很简单,把故障点标记一下,求最短路时被标记点不松弛即可。

Task2第一问比上面还简单,第二问是典型的次短路问题,考虑在做最短路时记录下最短路径,然后依次枚举删除最短路上的边,求新图的最短路的最小值就是原图的次短路。证明大概是这样:一定存在一条边在最短路径上但不在次短路径上,因此枚举出这条边,删除这条边后原来的最短路不复存在,但次短路可行,也就成了新的最短路。

【代码】

数据范围小,随便拿个最短路算法就能过。

http://paste.ubuntu.com/8136207/

评论

© OI技术宅 | Powered by LOFTER