A taxi meter charges per road. The map is directed: fares[i] = [u, v, cost] means you can ride from
u to v for cost (cost >= 0). Starting at start with budget money, return a sorted list of all
locations you can reach spending at most budget in total. The start itself always counts.
Examples
Input: n = 5, fares = [[0,1,3],[1,2,4],[0,3,10],[3,4,1],[2,4,1]], start = 0, budget = 8
Output: [0, 1, 2, 4]
Explanation: 1 costs 3, 2 costs 7, 4 costs 8 (via 2); 3 costs 10, too much.
Input: n = 3, fares = [[0,1,0],[1,2,1]], start = 0, budget = 0
Output: [0, 1]
Constraints
1 <= n <= 5000,0 <= len(fares) <= 10**4,0 <= budget <= 10**9- Target
O(E log V)time.
Goals
- Run Dijkstra on a directed graph and stop once distances exceed a limit
- Collect the settled set rather than a single distance
- Handle zero-cost edges and a zero budget