⚡Flashcard Drill➔
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

  1. This is Bellman-Ford with a round limit: after i rounds, dist holds the cheapest prices using at most i edges.
  2. With at most k stops, the path has at most k + 1 edges, so k + 1 rounds suffice.
  3. The copy is essential: relaxing in place would allow a path to use more than one edge per round.
  4. 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 k rounds instead of k + 1: k stops means k + 1 edges.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems