Loading...
Loading...
Loading...
Offices are joined by two-way links. Print one shortest route from office s to office t as office numbers separated by single spaces. When several routes are equally short, take the one found by a BFS that visits each office's neighbours in increasing order of number. Print NO PATH if t cannot be reached.
Example 1
Input
5 5 0 1 0 2 1 3 2 3 3 4 0 4
Output
0 1 3 4
Both 0 1 3 4 and 0 2 3 4 are shortest; the smaller neighbour 1 is taken first.
Example 2
Input
3 1 0 1 0 2
Output
NO PATH
Try the problem first. Open one hint at a time.
Sort every neighbour list so the order is fixed.
Store each node's parent and walk back from t, then reverse.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor