Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 2.0 seconds
Read in a directed graph which has been described as a list of edges, a source and a destination vertex and then output the shortest path between the source and the destination.
rule so that your results can be easily compared:
At any point if there is a choice of which vertex to visit, visit them in ascending numerical order
Eg: if a vertex's neighbours are 5,2,7 and 3 process them in the order 2, 3, 5 then 7.
Each vertex will be represented as a number from 0 to n-1 for n vertices.
The first line of input will state how many vertices are in the graph
The second line will specify the start and destination vertices
Each subsequent line will consist of pairs of numbers each describing an edge. The first number in the pair describes the vertex from where the edge originates and the second number states the vertex where the edge leads to.
The list will end with the end of the file.
Output the shortest path from the source to the destination as a list of vertices, on one line, separated by spaces.
1 <= n <= 1,000,000 and 0 <= total number of edges <= 1,000,000
Sample Input 1
3 2 1 0 1 1 0 1 2 0 2 2 0
Sample Output 1
2 0 1
Sample Input 2
10 5 5 1 2 2 3
Sample Output 2