Evil Dijkstra
Find the shortest path (that visits each vertex at most once) on a graph with all edge costs nonnegative.
InputThe graph has 15000 vertices, labeled 0...14999.
The first line of input is the number of edges.
For each edge, there is one line with three numbers: the starting vertex, the ending vertex, and the cost. The cost will not exceed 100000.
The graph will contain few enough edges that the input file can be read in a reasonable amount of time cin, at least; other methods should also work fine).
The first line of input is the number of edges.
For each edge, there is one line with three numbers: the starting vertex, the ending vertex, and the cost. The cost will not exceed 100000.
The graph will contain few enough edges that the input file can be read in a reasonable amount of time cin, at least; other methods should also work fine).
OutputOutput the shortest path from 0 to 1 as a sequence of nodes, separated by spaces, followed by a newline. Do not leave a trailing space. If there is a tie, output the lexicographically first shortest path.
If there is no path from 0 to 1, output ``No path'' followed by a newline.
If there is no path from 0 to 1, output ``No path'' followed by a newline.
Input:
Output:
7
0 1 6
0 2 1
2 6 1
6 4 1
4 1 1
2 3 0
3 4 2Output:
0 2 3 4 1Input:
Output:
5
0 4 1
1 4 1
2 3 1
3 5 1
7 199 1Output:
No pathSubmit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.