NeetCode #639LC-787MediumAdvanced GraphsNC 150NC 250
← Back to All Problems#639 · #787 · Cheapest Flights Within K Stops(K 站中转内最便宜的航班)
📌 Problem Statement & Constraints
You are given
n cities, flights where flights[i] = [from, to, price], and integers src, dst and k. Return the cheapest price from src to dst with at most k stops, or -1. Constraints: 1 <= n <= 100, 0 <= flights.length <= n * (n - 1) / 2, 0 <= k < n, prices are positive.💡 Core Algorithmic Approaches
- This is Bellman-Ford with a round limit: after
irounds,distholds the cheapest prices using at mostiedges. - With at most
kstops, the path has at mostk + 1edges, sok + 1rounds suffice. - The copy is essential: relaxing in place would allow a path to use more than one edge per round.
- The answer is
dist[dst], or -1 if it is still infinite.
💻 Benchmark Python3 Implementation
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
INF = float("inf")
dist = [INF] * n
dist[src] = 0
for _ in range(k + 1): # at most k stops -> k+1 edges
nxt = dist[:] # copy: one more edge per round
for u, v, w in flights:
if dist[u] + w < nxt[v]:
nxt[v] = dist[u] + w
dist = nxt
return dist[dst] if dist[dst] != INF else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O((k + 1) * E): one relaxation pass per allowed edge.
💾 Space Complexity
O(V) for the distance array.
⚠️ Interview Pitfalls & Follow-ups
- Relaxing in place: a path could use several edges in one round, exceeding the stop limit.
- Running
krounds instead ofk + 1:kstops meansk + 1edges. - Using Dijkstra: the stop limit is a second constraint that a plain shortest-path algorithm does not track.
- Using a visited set: a node may need to be revisited with a different stop count.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.