Routes between asked pairs

Fares can be negative. For each asked pair (i, j), return the stations of a cheapest route from i to j, in order, starting with i and ending with j; a station’s route to itself is [i]. Return None for a pair with no route. If any loop of fares adds up to less than 0, return None instead of a list, because then some pairs have no cheapest route.

cheapest_routes(3, [(0, 1, 4), (0, 2, 5), (2, 1, -3)],
                [(0, 1), (1, 0), (2, 2)])
# [[0, 2, 1], None, [2]]: 0 -> 2 -> 1 costs 5 - 3 = 2
cheapest_routes(3, [(0, 1, 1), (1, 2, -2), (2, 0, 0)], [(0, 2)])
# None: the loop 0 -> 1 -> 2 -> 0 costs -1

Any cheapest route passes: the tests report the cost of each route you give, or what is wrong with it. Lesson 5 describes the table of first steps that makes this cheap.

Limits

• Up to 150 stations, about 22,500 fares and 300 asked pairs.
• Aim for O(n³) (n · n · n steps) for the tables, then a few steps per route. The big tests have 5 seconds each.