提示: 欢迎访问OurACM平台。
Problem 1503 路由器的选择

Accept: 103    Submit: 284
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

在网络通信中,经常需要求最短路径。但完全用最短路径传输有这样一个问题:如果最终在两个终端节点之间给出的最短路径只有一条。则在该路径中的任一个节点或链路出现故障时,信号传输将面临中断的危险。因此,对网络路由选择作了以下改进:

为任意两节点之间通信提供三条路径供其选择,即最短路径、第二最短路径和第三最短路径。

第一最短路径定义为:给定一个不含负回路的网络D={V,A,W},其中V={v1,v2,…,vn},A 为边的集合,W 为权的集合,设P1 是D 中最短(v1,vn)路。称P1 为D 中最短(v1,vn)路径,如果D 中有一条(v1,vn)路,P2 满足以下条件:

 
(1)P2≠P1;
(2)D 中不存在异于P1 的路P,使得W(P1)≤W(P)< W(P2)

则称P2 为D 的第二最短路径。

第三最短路径的定义为:设P2 是D 中第二最短(v1,vn)路径,如果D 中有一条(v1,vn)路P3 满足以下条件:

 
(1)P3≠P2 并且P3≠P1;
(2)D 中不存在异于P1,P2 的路P,使得W(P2)≤W(P)< W(P3)

则称P3 为D 中第三最短路径。

现给定一有n 个节点的网络,n<=30,求给定两点间的第一、第二和第三最短路径。

Input

n S T Max (每格数值之间用空格分隔) M11 M12 … M1n M21 M22 … M2n …………………… Mn1 Mn2 … Mnn

其中n 为节点数,S 为起点,T 为终点,Max 为一代表无穷大的整数,Mij 描述I 到J 的距离,若Mij=Max,则表示从I 到J 无直接通路,Mii=0。

本题有多组数据。

Output

每组数据,输出一行3个整数,分别为三条路径长度(从小到大)。

Sample Input

5 1 5 10000 0 1 3 10000 7 10000 0 1 10000 10000 10000 10000 0 1 4 10000 10000 10000 0 1 10000 1 10000 10000 0

Sample Output

4 5 6

Source

FOJ月赛-2007年5月

Submit  Back  Status  Discuss