0101MediumDynamic ProgrammingDepth-First SearchBreadth-First SearchGraph TheoryHeap (Priority Queue)Shortest Path

Limited Handoff Courier Route

Tracked in this browser only

Trains the technique from

LeetCode 787Cheapest Flights Within K Stops

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 company sorts parcels at hubs depots numbered 0 through hubs - 1. The array legs lists the one-way truck runs it operates: legs[i] = [start, end, price] means a parcel can ride from depot start to depot end for price euros. A run only moves in the direction listed, and no ordered pair of depots has two runs between them.

A parcel is at depot origin and must reach depot destination. Every depot it is sorted at along the way counts as a handoff, and the contract allows at most max_handoffs of them, so the parcel may ride at most max_handoffs + 1 runs. The origin and the destination are not handoffs.

Return the smallest total price of a legal itinerary, or -1 when no itinerary obeys the handoff allowance.

Examples

Example 1

Input: hubs = 4, legs = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 3, 400]], origin = 0, destination = 3, max_handoffs = 1
Output: 400

Riding through depots 1 and 2 costs 150 but needs two handoffs, one more than allowed, so the parcel takes the single 400 euro run.

Example 2

Input: hubs = 4, legs = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 3, 400]], origin = 0, destination = 3, max_handoffs = 2
Output: 150

With two handoffs available the chain of three cheap runs is now legal and beats the direct run.

Example 3

Input: hubs = 3, legs = [[0, 1, 5]], origin = 0, destination = 2, max_handoffs = 2
Output: -1

Depot 2 has no incoming run at all, so no itinerary reaches it and the answer is the failure value.

Constraints

2 <= hubs <= 100
0 <= legs.length <= hubs * (hubs - 1) / 2
legs[i].length == 3
0 <= start, end < hubs
start != end
1 <= price <= 10^4
At most one run exists for any ordered pair (start, end)
0 <= origin, destination, max_handoffs < hubs
origin != destination

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_route(hubs: int, legs: list[list[int]], origin: int, destination: int, max_handoffs: int) -> int:

Java

public int cheapestRoute(int hubs, int[][] legs, int origin, int destination, int maxHandoffs)

The intended approach

Time O(max_handoffs * legs.length)Space O(hubs)

Track the cheapest known price to every depot using at most r runs, and grow r one run at a time up to `max_handoffs + 1`. Each round reads only the previous round's prices, written into a fresh copy, which is what keeps a single round from chaining several runs together and quietly overspending the handoff allowance. After the last round the entry for the destination is the answer.

Pythonentry point: cheapest_route

def cheapest_route(hubs, legs, origin, destination, max_handoffs):
    unreachable = float("inf")
    cost = [unreachable] * hubs
    cost[origin] = 0
    for _ in range(max_handoffs + 1):
        nxt = cost[:]
        for start, end, price in legs:
            if cost[start] + price < nxt[end]:
                nxt[end] = cost[start] + price
        cost = nxt
    return -1 if cost[destination] == unreachable else cost[destination]

The obvious version

Depth-first walk over every itinerary of at most max_handoffs + 1 runs, keeping the cheapest arrival at the destination. The depth cap makes it terminate even with cycles; exponential in the cap.

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_route(hubs, legs, origin, destination, max_handoffs):
    outgoing = {}
    for start, end, price in legs:
        outgoing.setdefault(start, []).append((end, price))
    best = [None]

    def walk(here, used, spent):
        if here == destination:
            if best[0] is None or spent < best[0]:
                best[0] = spent
            return
        if used == max_handoffs + 1:
            return
        for nxt, price in outgoing.get(here, []):
            walk(nxt, used + 1, spent + price)

    walk(origin, 0, 0)
    return -1 if best[0] is None else best[0]

How this problem was checked

Reference solution executed against 11 test cases — 11 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