Time limit: 10s
Memory limit: 32MB
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.
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
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.