Question

5733 - Graph_single source all destination

Time limit: 10s
Memory limit: 32MB
Problem Description

Given a directed graph with nonnegative edge costs, we want to compute a shortest path from a source vertex to each of the other vertices, The cost is 0 if source equals to destination. The vertex index is from 1 to n. You can use any algorithm but note that you should bound your program in O(n^2) to prevent time limit exceed error.

Input

The input consists of three parts.

First part is the 1 line: <#vertices > <#edges>
Second part is begin from 2 line to #edges+1:<Source ID> < Destination ID> < Edge Weight>
Third part is source vertex you need to compute.

P.S. The testcase range is from 1 vertex to 5000 vertices

Output

Please list the shortest path form the source vertex to all(except itself) vertex.
If the path is ∞ ,please use “INF” to represent,and show “No path from <source ID> to <destination ID>”.
If the shortest path is more than one , when you choose the shortest edge from each vertex, adjacent vertex with smaller ID should be prioritized within the same edge weight,there is an example for you to understand.

Sample Input

6 11
1 2 50
1 3 45
1 4 10
2 3 10
2 4 15
3 5 30
4 1 20
4 5 15
5 2 20
5 3 35
6 5 3
2
Sample Output

2..4..1..->35
2..3..->10
2..4..->15
2..4..5..->30
No path from 2 to 6->INF