Towns Within Fuel Budget
EasyAdvanced Graphs
Problem
A delivery drone is parked in town source. The region has n towns and two-way roads roads[i] = [u, v, fuel], where fuel is the energy needed to travel that road.
Return how many towns (including source) the drone can reach using at most budget units of fuel along a single route.
Example 1
- Input:
- n = 5, roads = [[0,1,3],[1,2,4],[0,3,8],[3,4,1],[2,4,2]], source = 0, budget = 8
- Output:
- 4
Cheapest costs: 0 → 0, 1 → 3, 2 → 7, 3 → 8, 4 → 9. Towns 0, 1, 2 and 3 fit in the budget.
Example 2
- Input:
- n = 3, roads = [[0,1,5]], source = 2, budget = 100
- Output:
- 1
Town 2 has no roads; only itself counts.
Example 3
- Input:
- n = 3, roads = [[0,1,0],[1,2,1]], source = 0, budget = 0
- Output:
- 2
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ roads.length ≤ 2·10^4
- 0 ≤ fuel ≤ 10^4
- 0 ≤ budget ≤ 10^9
Hint
Show the first hint
A town is in range exactly when its cheapest route costs at most the budget.
Walkthrough
How to approach it
01Clarify before coding
- Is the budget per route or for visiting all towns in one trip? Per route: each town is judged on its own cheapest route.
- Does the source count? Yes.
- Can fuel be zero? Yes, but never negative.
02Brute force
BFS/DFS over every route, abandoning a route once it exceeds the budget.
Cost: Exponential: the same town is re-explored along every route that reaches it under budget.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.