Funcia
Lv.3bellman-forddpgraphshortest-path

Cheapest Flight Within K Stops

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

There are n airports numbered 0 to n - 1. flights[i] = [a, b, price] is a direct flight from airport a to airport b costing price (the reverse direction is a separate flight, if any).

Travel from src to dst with at most k intermediate stops, i.e. taking at most k + 1 flights. Return the cheapest total price, or -1 if it is impossible.

Examples

nflightssrcdstkresult
4[[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 2, 650], [1, 3, 600]]031700
4[[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 2, 650], [1, 3, 600]]032300
3[[0, 1, 5], [1, 2, 5]]020-1

Example 1 — With one stop: 0 → 1 → 3 costs 700 and 0 → 2 → 3 costs 750.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(n: int, flights: int[][], src: int, dst: int, k: int) → int

Constraints

  • 2≤2 \le n ≤1,000\le 1{,}000
  • 0≤M=0 \le M = flights.length ≤6,000\le 6{,}000, 0≤0 \le a, b <n< n, a ≠\ne b, 1≤1 \le price ≤106\le 10^6; parallel flights may appear
  • 0≤0 \le src, dst <n< n, src ≠\ne dst, 0≤0 \le k <n< n

Expected complexity

Time
O(K * (N + M))
Space
O(N + M)

Examples

nflightssrcdstkExpected
4[[0,1,100],[1,2,100],[2,3,100],[0,2,650],[1,3,600]]031700
4[[0,1,100],[1,2,100],[2,3,100],[0,2,650],[1,3,600]]032300
3[[0,1,5],[1,2,5]]020-1

Hint

Hint

Plain Dijkstra ignores the flight-count limit. Run Bellman–Ford for exactly k + 1 rounds, relaxing every flight from the previous round's costs only (a copy), so each round adds at most one flight; cost[dst] after the last round is the answer. Scanning an n×nn \times n price table in every round is O(k⋅n2)O(k \cdot n^2) and exceeds the time limit; O(k⋅(n+M))O(k \cdot (n + M)) is enough.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.