最短路径

Time Limit:3000MS  Memory Limit:65536K
Total Submit:9 Accepted:0 

Description 

Given a directed graph G=(V, E), and a source vertex v0, please write a program to output the lengths of the shortest paths between v0 and all other vertices in the graph G. We assume the edges in digraph G can have negative costs, provided that the sum of the costs around any cycle in the digraph is positiv. The vertices are labeled from 1 to n, if G has n vertices. The data fromats of the input and the output of this problem are arranged as follows. 



Input 

Your program must accept the following input data: 

1、A positive integer n, it stands for the total number vertices of G. 
2、A source vertex v0. It could be any vertex in G. 
3、The cost matrix W of G. It is arranged by row-wise order as follows. 
the first row of cost matrix W (enter) 
the second row of cost matrix W (enter) 
... 
the last row of cost matrix W (enter) 

Your program must be able to accept multiple sets of data. 


Output 


The lengths of the shortest paths from v0 to all other vertices vi, the format is v0 ->vi) = ? If there is no path in the graph between those two verices do not output the corresponding line.



Seperate different sets of data by a blank line.


Notes 



In the input, we arrange the input data W(vi,vj) = '-', if (vi, vj)is not an edge in G, and W(vi, vj) = 0, if vi =vj. 

Your program must be able to accept the multiple set of input data. 


Sample Input 


Assume we have the following 5-vertex digraph G and its cost matrix W.

If we let v0 = 1, then yout input data must be

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

Sample Output 


(2 -> 3) = 3
(2 -> 4) = 7
(2 -> 5) = 7

Source 
我的邮箱是:  lt_xz@163.com