Show problems as
Classic problem #787MediumDynamic ProgrammingDepth-First SearchBreadth-First SearchGraph TheoryHeap (Priority Queue)Shortest Path

Cheapest Flights Within K Stops

Real-world version: Limited Handoff Courier Route
Tracked in this browser only
Read Cheapest Flights Within K Stops on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstWith Graphs · Priority Queues, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard 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)

More on the same topics