The courier's route
A courier picked up an order at crossing 1 and has to deliver it to crossing n. The city is n crossings and m streets; every street joins two crossings, can be driven both ways, and its length in metres is known. Find the shortest route and print it in full—the courier's navigator has to show where to turn.
One of the tests is the real Almaty from OpenStreetMap: crossing 1 is by Republic Square, crossing n by the Green Bazaar.
Input
The first line holds n and m (2 ≤ n ≤ 50,000, 1 ≤ m ≤ 100,000). Each of the next m lines holds three numbers a, b, w: a street between crossings a and b, w metres long (1 ≤ a, b ≤ n, 1 ≤ w ≤ 10,000). Two crossings may be joined by several streets, and a street may loop back to the crossing it started from.
Output
If the order cannot be reached, print -1. Otherwise print the length of the shortest route on the first line, the number k of crossings on it (the first and the last included) on the second, and the crossings themselves in order, from 1 to n, on the third. If there are several shortest routes, any of them will do.
Examples
Example 1
6 9 1 2 7 1 3 9 1 6 14 2 3 10 2 4 15 3 4 11 3 6 2 4 5 6 5 6 9
11 3 1 3 6
Example 2
4 2 1 2 5 3 4 1
-1
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Breadth-first search finds the route with the fewest streets. But a 10 km street and a 10 m street are the same to it. Look at the second example: which route would breadth-first search pick, and which one is needed?
2Hint 2
Besides the length, the route itself is needed. When you improve the distance to a crossing, remember where you came from. How do you then walk these records from the finish back to the start?
3The idea
This is the classic Dijkstra's algorithm: lengths are positive and we need the shortest path from one vertex. To rebuild the route we keep a parent array: on every successful relaxation of an edge (u, v) we record parent[v] = u. The last record for v belongs to its final distance—once v is out of the heap, its distance no longer changes.
4Walkthrough
Read the graph into adjacency lists, adding every street in both directions. Run Dijkstra from 1 with a binary heap and lazy deletion. As soon as n comes out of the heap we can stop: its distance is final.
If dist[n] stayed infinite, print −1. Otherwise walk from n along parent until you reach 1 and reverse the list. No recursion is needed here, and it would even hurt: in one test the route passes through 50,000 crossings, and a recursive rebuild hits Python's stack depth limit.
Loops and repeated streets break nothing: a loop never improves a distance (its length is positive), and of several streets between one pair of crossings, relaxation picks the shortest by itself.
4+Solution
5Complexity
O((n + m) log n) time and O(n + m) memory. With m = 10⁵ that is about two million elementary steps—a fraction of a second even in Python.
6Common mistakes
- Breadth-first search instead of Dijkstra. Passes the first example, where the shortest routes happen to have the fewest streets too, and fails the second test, where one long street leads straight to the target.
- Marking “visited” when pushing onto the heap. That is how breadth-first search does it, but in Dijkstra a vertex can improve after it first entered the heap. Mark it when it is popped.
- Slow input in Python. A hundred thousand calls to
input()are much slower than onesys.stdin.buffer.read(). See the technique fast input and output. - Rebuilding the route recursively. A chain of 50,000 crossings raises
RecursionError.