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

## Comments

## Leave a comment