The fastest journey

Find the fastest journey from station s to station t. Return a pair (time, route), where time is the least number of minutes and route is a list of stations from s to t that takes exactly that time. Return None if t cannot be reached.

edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2),
         (1, 3, 1), (2, 3, 5), (3, 4, 3)]
fastest(5, edges, 0, 4)   # (7, [0, 2, 1, 3, 4])
fastest(5, edges, 4, 0)   # None
fastest(5, edges, 2, 2)   # (0, [2])

Lines are one-way, and times are whole numbers from 0 up. When several routes are equally fast, any of them is accepted: the tests add up the times of your route’s lines and compare them with your time and with the least time.

Limits

• Up to 102,002 stations and 200,000 lines.
• Looking through every station to find the nearest one is too slow here, and so is handling a station again for every old entry it left in the heap. The big tests have 3 or 4 seconds each.