Towns Within Budget
A county has n towns numbered 0 to n - 1. roads is a list of entries [a, b, fee] with a != b: a road between towns a and b that can be driven in both directions for a fee of fee. Several roads may join the same two towns at different fees. The cost of reaching a town is the smallest total fee of any trip from start to it; reaching start costs 0.
Return how many towns can be reached from start for a cost of at most budget, counting start itself.
Example 1
n 5
roads [[0,1,4],[1,2,3],[0,2,10],[2,3,1],[3,4,20]]
start 0
budget 8
returns 4
The cheapest costs from 0 are 0, 4, 7, 8 and 28; four of them are at most 8.
Example 2
n 3
roads [[0,1,5]]
start 0
budget 4
returns 1
Town 1 costs 5, which is over the budget, so only 0 counts.
Constraints
1 <= n <= 500 <= len(roads) <= 1000 <= a, b <= n - 1anda != b1 <= fee <= 1000 <= start <= n - 10 <= budget <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.