FunctionRacerProblemsRace

Towns Within Budget

MediumGraphsPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems