Problem 1929. -- 最短路径

1929: 最短路径

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 153  Accepted: 17
[Submit][Status][Web Board]

Description

给出一个有向图G=(V, E),和一个源点v0∈V,请写一个程序输出v0和图G中其它顶点的最短路径。只要所有的有向环都是正的,我们就允许图的边有负值。顶点的标号从1到n(n为图G的顶点数)。

Input

包含多组测试数据。
第1行:一个正数n(2<=n<=80),表示图G的顶点总数。
第2行:一个整数,表示源点v0(v0∈V,v0可以是图G中任意一个顶点)。
第3至第n+2行,用一个邻接矩阵W给出了这个图。
如果顶点i到顶点j有变存在,其权值为k,在矩阵对应位置为k,否则矩阵对应位置为“-”。

Output

每组测试数据包含n-1行,按照顶点编号从小到大的顺序,每行输出源点v0到一个顶点的最短距离。每行的具体格式参照样例。

Sample Input

5
1
0 2 - - 10
- 0 3 - 7
- - 0 4 -
- - - 0 5
- - 6 - 0

Sample Output

(1->2)=2
(1->3)=5
(1->4)=9
(1->5)=9

Source

[Submit][Status][Web Board]