0460HardArrayDynamic ProgrammingGraph TheoryDijkstra's Algorithm

Cheapest Run Inside The Shift

Tracked in this browser only

Trains the technique from

LeetCode 1928Minimum Cost to Reach Destination in Time

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A courier starts at depot 0 and must finish at depot n - 1, where n is the length of tolls. Each row of links is [a, b, minutes], a road that can be driven in either direction and takes minutes to drive. Two depots may be joined by more than one road, and no road loops a depot back to itself.

tolls[j] is the gate charge at depot j. The charge is paid on arriving at a depot, and it is paid again on every later arrival there, so a depot passed through twice is charged twice. The charge at the starting depot is paid before setting off.

The whole run must take at most budget minutes of driving; time spent standing at a depot does not count. Return the smallest total of gate charges for a run that finishes at depot n - 1 inside the budget, or -1 if no run manages it. Gate charges are at least 1, so a real total is never -1.

Examples

Example 1

Input: budget = 8, links = [[0, 1, 1], [1, 3, 1], [0, 2, 4], [2, 3, 4]], tolls = [2, 40, 3, 5]
Output: 10

With 8 minutes to play with the courier can drive 0 to 2 to 3, taking all 8 minutes and paying 2 at the start, 3 at depot 2 and 5 at depot 3.

Example 2

Input: budget = 2, links = [[0, 1, 1], [1, 3, 1], [0, 2, 4], [2, 3, 4]], tolls = [2, 40, 3, 5]
Output: 47

Only 2 minutes are available, so the run 0 to 1 to 3 is the one that fits, paying 2 then 40 then 5.

Example 3

Input: budget = 5, links = [[0, 1, 6], [1, 2, 1]], tolls = [4, 7, 9]
Output: -1

The only road out of depot 0 takes 6 minutes on its own, which is already past the budget, so the courier cannot finish the run.

Constraints

1 <= budget <= 1000
n == tolls.length
2 <= n <= 1000
n - 1 <= links.length <= 1000
links[i].length == 3
0 <= a_i, b_i <= n - 1
a_i != b_i
1 <= minutes_i <= 1000
1 <= tolls[j] <= 1000

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def cheapest_run(budget: int, links: list[list[int]], tolls: list[int]) -> int:

Java

public int cheapestRun(int budget, int[][] links, int[] tolls)

The intended approach

Time O(budget * m) for m roads: each minute count relaxes every road in both directions.Space O(budget * n) for the table of totals.

Track the cheapest total for every pair of (minutes already driven, depot reached). Keeping the minutes in the state is what makes it work, because a dearer arrival that happens sooner leaves more budget for the rest of the run and can beat a cheaper, slower one. Sweep the minute counts upwards, pushing each recorded total along every road that still fits in the budget, then take the smallest total recorded at the last depot over all minute counts.

Pythonentry point: cheapest_run

def cheapest_run(budget, links, tolls):
    # State is (minutes spent, depot reached), not depot alone: an arrival that
    # costs more but happens sooner can still be the one that pays off later.
    # O(budget * m) time for m links, O(budget * n) space.
    n = len(tolls)
    INF = float("inf")
    best = [[INF] * n for _ in range(budget + 1)]
    best[0][0] = tolls[0]
    for spent in range(budget + 1):
        row = best[spent]
        for a, b, mins in links:
            for u, v in ((a, b), (b, a)):
                here = row[u]
                if here == INF:
                    continue
                later = spent + mins
                if later > budget:
                    continue
                cand = here + tolls[v]
                if cand < best[later][v]:
                    best[later][v] = cand
    answer = INF
    for spent in range(budget + 1):
        if best[spent][n - 1] < answer:
            answer = best[spent][n - 1]
    return -1 if answer == INF else answer

The obvious version

Grow every run out of depot 0 that stays inside the budget, adding gate charges as it goes, and keep the smallest total seen at the last depot. Exponential in the budget.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_cheapest_run(budget, links, tolls):
    n = len(tolls)
    near = [[] for _ in range(n)]
    for a, b, mins in links:
        near[a].append((b, mins))
        near[b].append((a, mins))
    best = [None]
    stack = [(0, 0, tolls[0])]
    while stack:
        at, spent, paid = stack.pop()
        if at == n - 1:
            if best[0] is None or paid < best[0]:
                best[0] = paid
        for nxt, mins in near[at]:
            if spent + mins <= budget:
                stack.append((nxt, spent + mins, paid + tolls[nxt]))
    return -1 if best[0] is None else best[0]

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in