A travel agent sells tickets on one-way coach lines between n towns 0 .. n-1:
lines[i] = [a, b, fare] goes from town a to town b. Several lines may join the same pair of
towns, and a line may start and end in the same town.
An itinerary from src to dst is any sequence of lines, each starting where the previous one
ended; towns and lines may be repeated. Two itineraries are different if their sequences of line
indices differ. If src == dst, the empty itinerary (cost 0) counts.
Return the costs of the k cheapest itineraries as a list in non-decreasing order (equal costs
appear once per itinerary). If fewer than k itineraries exist, return all of their costs.
Examples
Input: n = 3, lines = [[0,1,1],[1,2,1],[0,2,3],[1,0,1]], src = 0, dst = 2, k = 4
Output: [2, 3, 4, 5]
Explanation: 0-1-2 costs 2, 0-2 costs 3, 0-1-0-1-2 costs 4, 0-1-0-2 costs 5.
Input: n = 3, lines = [[0,1,2],[1,2,2],[0,2,4]], src = 0, dst = 2, k = 5
Output: [4, 4]
Input: n = 2, lines = [[0,1,1],[1,0,2]], src = 0, dst = 0, k = 3
Output: [0, 3, 6]
Constraints
1 <= n <= 10**4,0 <= len(lines) <= 3 * 10**4,1 <= fare <= 1000,1 <= k <= 20
Goals
- Let a node leave the heap more than once
- Prove that the j-th time a node is popped gives its j-th cheapest walk
- Cap the pops per node to keep the heap small