Skip to content
BASA DSA

Cheapest Flights Within K Stops

MediumAdvanced Graphs

Flights are directed [from,to,price] edges. Return the lowest total price from src to dst using at most k intermediate stops (at most k+1 edges), or -1 if impossible.

Example 1

Directed flight prices; 0 → 2, at most 1 stops.Directed flight prices; 0 → 2, at most 1 stops. Vertices: node 0: 0, node 1: 1, node 2: 2. Edges: node 0 (0) → node 1 (1) (20); node 1 (1) → node 2 (2) (30); node 0 (0) → node 2 (2) (90).203090012
Directed flight prices; 0 → 2, at most 1 stops.

Input
n = 3
flights = [[0,1,20],[1,2,30],[0,2,90]]
src = 0
dst = 2
k = 1
Output
50

Explanation

One stop allows 0->1->2 for 20+30=50, beating the direct cost 90.

Example 2

Directed flight prices; 0 → 2, at most 0 stops.Directed flight prices; 0 → 2, at most 0 stops. Vertices: node 0: 0, node 1: 1, node 2: 2. Edges: node 0 (0) → node 1 (1) (20); node 1 (1) → node 2 (2) (30); node 0 (0) → node 2 (2) (90).203090012
Directed flight prices; 0 → 2, at most 0 stops.

Input
n = 3
flights = [[0,1,20],[1,2,30],[0,2,90]]
src = 0
dst = 2
k = 0
Output
90

Explanation

Zero stops permits only the direct flight costing 90.

Example 3

Directed flight prices; 0 → 2, at most 2 stops.Directed flight prices; 0 → 2, at most 2 stops. Vertices: node 0: 0, node 1: 1, node 2: 2. Edges: node 0 (0) → node 1 (1) (10).10012
Directed flight prices; 0 → 2, at most 2 stops.

Input
n = 3
flights = [[0,1,10]]
src = 0
dst = 2
k = 2
Output
-1

Explanation

No flight path reaches node 2 under any stop allowance.

Constraints

  • 2 <= n <= 100
  • Node IDs are 0..n-1
  • Positive prices <= 10000
  • 0 <= k < n
  • src differs from dst

Function contractfindCheapestPriceArguments: json, json, json, json, json
Loading draft…
SolutionRuns on your device