787. Cheapest Flights Within K Stops - Explanation

Description

There are n airports, labeled from 0 to n - 1, which are connected by some flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] represents a one-way flight from airport from_i to airport to_i with cost price_i. You may assume there are no duplicate flights and no flights from an airport to itself.

You are also given three integers src, dst, and k where:

src is the starting airport
dst is the destination airport
src != dst
k is the maximum number of stops you can make (not including src and dst)

Return the cheapest price from src to dst with at most k stops, or return -1 if it is impossible.

Example 1:

Input: n = 4, flights = [[0,1,200],[1,2,100],[1,3,300],[2,3,100]], src = 0, dst = 3, k = 1

Output: 500

Explanation:
The optimal path with at most 1 stop from airport 0 to 3 is shown in red, with total cost 200 + 300 = 500.
Note that the path [0 -> 1 -> 2 -> 3] costs only 400, and thus is cheaper, but it requires 2 stops, which is more than k.

Example 2:

Input: n = 3, flights = [[1,0,100],[1,2,200],[0,2,100]], src = 1, dst = 2, k = 1

Output: 200

Explanation:
The optimal path with at most 1 stop from airport 1 to 2 is shown in red and has cost 200.

Constraints:

1 <= n <= 100
fromi != toi
1 <= pricei <= 1000
0 <= src, dst, k < n

Topics

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n + (m * k)) time and O(n) space, where n is the number of cities, m is the number of flights, and k is the number of stops.

Hint 1

Consider this as a graph problem where the cities are nodes and the flights are edges connecting two cities, with the ticket cost as the edge weight. Can you think of a shortest path algorithm to solve the problem? Perhaps a better algorithm than Dijkstra's that can intuitively handle the k stops condition.

Hint 2

We can use the Bellman-Ford algorithm. Initialize a prices array of size n with Infinity, setting prices[source] = 0. These values describe the cost to reach a city from the source city. Iterate (k + 1) times (stops are 0-indexed), updating the cost to each city by extending paths from cities with valid costs. We only update the cost for a city if it is less than the previous cost. How would you implement this?

Hint 3

At each level of iteration, we go through the given flights and use them to update the price array with the minimum costs compared to the previous level. We use a temporary prices array at each level to store the updated costs. After completing all levels, we return the result stored in prices[dst]. If that value is Infinity, we return -1 instead.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Graph Representation - Building adjacency lists to represent weighted directed graphs
Dijkstra's Algorithm - Finding shortest paths in weighted graphs using a min-heap/priority queue
Bellman-Ford Algorithm - Relaxing edges iteratively to find shortest paths with edge count constraints
Priority Queue/Min-Heap - Efficiently extracting minimum cost states during graph traversal

1. Dijkstra's Algorithm

Intuition

We want the cheapest cost to go from src to dst, but we can take at most k stops (so at most k+1 flights/edges).
Normal Dijkstra finds the cheapest path, but it ignores stop limits.
So we treat a "state" as: (current city, how many stops used).
That way, reaching the same city with different stop counts is considered different, and we can enforce the limit.

We always expand the currently cheapest state first using a min-heap.
The first time we pop dst, that cost is the cheapest possible within the allowed stops.

Algorithm

Build adjacency list: for each flight u -> v with price w.
Create dist[city][stopsUsed] = bestCost (initialize to infinity).
Push (0, src, -1) into a min-heap, meaning cost 0 at src with "-1 stops so far" (so first flight makes stops = 0).
While heap not empty:
- Pop (cost, city, stops).
- If city == dst, return cost.
- If stops == k, you can't take more flights, continue.
- If this cost is worse than the best recorded for this (city, stops+1) state, skip.
- For each neighbor (nextCity, price):
  - nextCost = cost + price
  - nextStops = stops + 1
  - If nextCost improves dist[nextCity][nextStops+1], update it and push into heap.
If the heap empties without reaching dst, return -1.

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        INF = float("inf")
        adj = [[] for _ in range(n)]
        dist = [[INF] * (k + 5) for _ in range(n)]
        for u, v, cst in flights:
            adj[u].append([v, cst])

        dist[src][0] = 0
        minHeap = [(0, src, -1)] # cost, node, stops
        while len(minHeap):
            cst, node, stops = heapq.heappop(minHeap)
            if dst == node: return cst
            if stops == k or dist[node][stops + 1] < cst:
                continue
            for nei, w in adj[node]:
                nextCst = cst + w
                nextStops = 1 + stops
                if dist[nei][nextStops + 1] > nextCst:
                    dist[nei][nextStops + 1] = nextCst
                    heapq.heappush(minHeap, (nextCst, nei, nextStops))

        return -1

public class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int INF = Integer.MAX_VALUE;
        List<int[]>[] adj = new ArrayList[n];
        int[][] dist = new int[n][k + 5];
        for (int i = 0; i < n; i++) Arrays.fill(dist[i], INF);

        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] flight : flights) {
            adj[flight[0]].add(new int[]{flight[1], flight[2]});
        }

        dist[src][0] = 0;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[0])
        );
        minHeap.offer(new int[]{0, src, -1});

        while (!minHeap.isEmpty()) {
            int[] top = minHeap.poll();
            int cst = top[0], node = top[1], stops = top[2];
            if (node == dst) return cst;
            if (stops == k || dist[node][stops + 1] < cst) continue;
            for (int[] neighbor : adj[node]) {
                int nei = neighbor[0], w = neighbor[1];
                int nextCst = cst + w;
                int nextStops = stops + 1;
                if (dist[nei][nextStops + 1] > nextCst) {
                    dist[nei][nextStops + 1] = nextCst;
                    minHeap.offer(new int[]{nextCst, nei, nextStops});
                }
            }
        }
        return -1;
    }
}

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        int INF = 1e9;
        vector<vector<pair<int, int>>> adj(n);
        vector<vector<int>> dist(n, vector<int>(k + 5, INF));

        for (auto& flight : flights) {
            adj[flight[0]].emplace_back(flight[1], flight[2]);
        }

        dist[src][0] = 0;
        priority_queue<tuple<int, int, int>,
                       vector<tuple<int, int, int>>, greater<>> minHeap;
        minHeap.emplace(0, src, -1);

        while (!minHeap.empty()) {
            auto [cst, node, stops] = minHeap.top();
            minHeap.pop();
            if (node == dst) return cst;
            if (stops == k || dist[node][stops + 1] < cst) continue;
            for (auto& [nei, w] : adj[node]) {
                int nextCst = cst + w;
                int nextStops = stops + 1;
                if (dist[nei][nextStops + 1] > nextCst) {
                    dist[nei][nextStops + 1] = nextCst;
                    minHeap.emplace(nextCst, nei, nextStops);
                }
            }
        }
        return -1;
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number[][]} flights
     * @param {number} src
     * @param {number} dst
     * @param {number} k
     * @return {number}
     */
    findCheapestPrice(n, flights, src, dst, k) {
        const INF = Infinity;
        const adj = Array.from({ length: n }, () => []);
        const dist = Array.from({ length: n }, () => Array(k + 5).fill(INF));

        for (let [u, v, cst] of flights) {
            adj[u].push([v, cst]);
        }

        dist[src][0] = 0;
        const minHeap = new MinPriorityQueue((entry) => entry[0]);
        minHeap.push([0, src, -1]); // cost, node, stops
        while (!minHeap.isEmpty()) {
            const [cst, node, stops] = minHeap.pop();
            if (node === dst) return cst;
            if (stops === k || dist[node][stops + 1] < cst) continue;
            for (let [nei, w] of adj[node]) {
                const nextCst = cst + w;
                const nextStops = stops + 1;
                if (dist[nei][nextStops + 1] > nextCst) {
                    dist[nei][nextStops + 1] = nextCst;
                    minHeap.push([nextCst, nei, nextStops]);
                }
            }
        }
        return -1;
    }
}

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int INF = int.MaxValue;
        List<int[]>[] adj = new List<int[]>[n];
        int[][] dist = new int[n][];

        for (int i = 0; i < n; i++) {
            adj[i] = new List<int[]>();
            dist[i] = new int[k + 2];
            Array.Fill(dist[i], INF);
        }

        foreach (var flight in flights) {
            adj[flight[0]].Add(new int[] { flight[1], flight[2] });
        }

        dist[src][0] = 0;
        var minHeap = new PriorityQueue<(int cst, int node, int stops), int>();
        minHeap.Enqueue((0, src, 0), 0);

        while (minHeap.Count > 0) {
            var (cst, node, stops) = minHeap.Dequeue();
            if (dist[node][stops] < cst) continue;
            if (node == dst) return cst;
            if (stops > k) continue;

            foreach (var neighbor in adj[node]) {
                int nei = neighbor[0], w = neighbor[1];
                int nextCst = cst + w;
                int nextStops = stops + 1;

                if (dist[nei][nextStops] > nextCst) {
                    dist[nei][nextStops] = nextCst;
                    minHeap.Enqueue((nextCst, nei, nextStops), nextCst);
                }
            }
        }
        return -1;
    }
}

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    INF := 1000000000
    adj := make([][]struct{ to, cost int }, n)
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, k+5)
        for j := range dist[i] {
            dist[i][j] = INF
        }
    }
    for _, flight := range flights {
        from, to, cost := flight[0], flight[1], flight[2]
        adj[from] = append(adj[from], struct{ to, cost int }{to, cost})
    }
    dist[src][0] = 0
    minHeap := priorityqueue.NewWith(func(a, b interface{}) int {
        return utils.IntComparator(a.([3]int)[0], b.([3]int)[0])
    })
    minHeap.Enqueue([3]int{0, src, -1})
    for !minHeap.Empty() {
        value, _ := minHeap.Dequeue()
        cst, node, stops := value.([3]int)[0], value.([3]int)[1], value.([3]int)[2]
        if node == dst {
            return cst
        }
        if stops == k || dist[node][stops+1] < cst {
            continue
        }
        for _, nei := range adj[node] {
            nextCst := cst + nei.cost
            nextStops := stops + 1
            if dist[nei.to][nextStops+1] > nextCst {
                dist[nei.to][nextStops+1] = nextCst
                minHeap.Enqueue([3]int{nextCst, nei.to, nextStops})
            }
        }
    }
    return -1
}

class Solution {
    fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {
        val INF = 1_000_000_000
        val adj = Array(n) { mutableListOf<Pair<Int, Int>>() }
        val dist = Array(n) { IntArray(k + 5) { INF } }
        for (flight in flights) {
            adj[flight[0]].add(Pair(flight[1], flight[2]))
        }
        dist[src][0] = 0
        val minHeap = PriorityQueue(compareBy<Triple<Int, Int, Int>> { it.first })
        minHeap.add(Triple(0, src, -1))
        while (minHeap.isNotEmpty()) {
            val (cst, node, stops) = minHeap.poll()
            if (node == dst) return cst
            if (stops == k || dist[node][stops + 1] < cst) continue
            for ((nei, w) in adj[node]) {
                val nextCst = cst + w
                val nextStops = stops + 1
                if (dist[nei][nextStops + 1] > nextCst) {
                    dist[nei][nextStops + 1] = nextCst
                    minHeap.add(Triple(nextCst, nei, nextStops))
                }
            }
        }
        return -1
    }
}

struct Item: Comparable {
    let cost: Int
    let node: Int
    let stops: Int

    static func < (lhs: Item, rhs: Item) -> Bool {
        return lhs.cost < rhs.cost
    }
}

class Solution {
    func findCheapestPrice(_ n: Int, _ flights: [[Int]], _ src: Int, _ dst: Int, _ k: Int) -> Int {
        let INF = Int.max
        var adj = Array(repeating: [(Int, Int)](), count: n)
        var dist = Array(repeating: Array(repeating: INF, count: k + 5), count: n)

        for flight in flights {
            let u = flight[0], v = flight[1], cst = flight[2]
            adj[u].append((v, cst))
        }

        var minHeap = Heap<Item>()
        minHeap.insert(Item(cost: 0, node: src, stops: -1))
        dist[src][0] = 0

        while !minHeap.isEmpty {
            let item = minHeap.removeMin()
            let cst = item.cost, node = item.node, stops = item.stops
            if node == dst { return cst }
            if stops == k || dist[node][stops + 1] < cst { continue }

            for (nei, w) in adj[node] {
                let nextCst = cst + w
                let nextStops = stops + 1
                if dist[nei][nextStops + 1] > nextCst {
                    dist[nei][nextStops + 1] = nextCst
                    minHeap.insert(Item(cost: nextCst, node: nei, stops: nextStops))
                }
            }
        }

        return -1
    }
}

impl Solution {
    pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
        let n = n as usize;
        let src = src as usize;
        let dst = dst as usize;
        let inf = i32::MAX;
        let mut adj = vec![vec![]; n];
        let mut dist = vec![vec![inf; (k + 5) as usize]; n];

        for flight in &flights {
            adj[flight[0] as usize].push((flight[1] as usize, flight[2]));
        }

        dist[src][0] = 0;
        let mut min_heap = BinaryHeap::new();
        min_heap.push(Reverse((0, src, -1i32)));

        while let Some(Reverse((cst, node, stops))) = min_heap.pop() {
            if node == dst { return cst; }
            if stops == k || dist[node][(stops + 1) as usize] < cst { continue; }
            for &(nei, w) in &adj[node] {
                let next_cst = cst + w;
                let next_stops = stops + 1;
                if dist[nei][(next_stops + 1) as usize] > next_cst {
                    dist[nei][(next_stops + 1) as usize] = next_cst;
                    min_heap.push(Reverse((next_cst, nei, next_stops)));
                }
            }
        }

        -1
    }
}

Time & Space Complexity

Time complexity: $O(n \cdot K + m \cdot K \cdot \log(m \cdot K))$ , commonly written as $O(m \cdot k \cdot \log(m \cdot k))$
Space complexity: $O(m + n \cdot K + m \cdot K)$

Where $n$ is the number of cities, $m$ is the number of flights, and $K = k + 1$ is the maximum number of flights/edges allowed. The layered graph has $O(n \cdot K)$ states and $O(m \cdot K)$ transitions. With the lazy priority queue used here, each successful relaxation can push one heap entry, so the heap operation cost is $\log(m \cdot K)$ , and the heap can hold $O(m \cdot K)$ entries in the worst case. The adjacency list takes $O(m)$ space and dist takes $O(n \cdot K)$ space.

2. Bellman Ford Algorithm

Intuition

We are allowed at most k stops, which means at most k + 1 flights (edges).
Bellman–Ford is perfect here because it relaxes edges level by level, where each iteration allows one more edge in the path.

Key idea:

After i iterations, we know the cheapest cost to reach every city using at most i flights.
By running the relaxation k + 1 times, we ensure we only consider paths that respect the stop limit.
We use a temporary array each iteration so that paths from the same iteration don't chain together and accidentally exceed the allowed number of flights.

Algorithm

Initialize prices array with infinity, set prices[src] = 0.
Repeat k + 1 times:
- Make a copy tmpPrices = prices.
- For every flight (s -> d, cost):
  - If prices[s] is reachable:
    - Try relaxing the edge: tmpPrices[d] = min(tmpPrices[d], prices[s] + cost)
- Assign prices = tmpPrices.
After all iterations:
- If prices[dst] is still infinity, return -1.
- Otherwise, return prices[dst].

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        prices = [float("inf")] * n
        prices[src] = 0

        for i in range(k + 1):
            tmpPrices = prices.copy()

            for s, d, p in flights:  # s=source, d=dest, p=price
                if prices[s] == float("inf"):
                    continue
                if prices[s] + p < tmpPrices[d]:
                    tmpPrices[d] = prices[s] + p
            prices = tmpPrices
        return -1 if prices[dst] == float("inf") else prices[dst]

public class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] prices = new int[n];
        Arrays.fill(prices, Integer.MAX_VALUE);
        prices[src] = 0;

        for (int i = 0; i <= k; i++) {
            int[] tmpPrices = Arrays.copyOf(prices, n);

            for (int[] flight : flights) {
                int s = flight[0];
                int d = flight[1];
                int p = flight[2];

                if (prices[s] == Integer.MAX_VALUE) {
                    continue;
                }

                if (prices[s] + p < tmpPrices[d]) {
                    tmpPrices[d] = prices[s] + p;
                }
            }

            prices = tmpPrices;
        }

        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> prices(n, INT_MAX);
        prices[src] = 0;

        for (int i = 0; i <= k; i++) {
            vector<int> tmpPrices = prices;

            for (const auto& flight : flights) {
                int s = flight[0];
                int d = flight[1];
                int p = flight[2];

                if (prices[s] == INT_MAX)
                    continue;

                if (prices[s] + p < tmpPrices[d])
                    tmpPrices[d] = prices[s] + p;
            }

            prices = tmpPrices;
        }

        return prices[dst] == INT_MAX ? -1 : prices[dst];
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number[][]} flights
     * @param {number} src
     * @param {number} dst
     * @param {number} k
     * @return {number}
     */
    findCheapestPrice(n, flights, src, dst, k) {
        let prices = new Array(n).fill(Number.MAX_SAFE_INTEGER);
        prices[src] = 0;

        for (let i = 0; i <= k; i++) {
            const tmpPrices = [...prices];

            for (const flight of flights) {
                const s = flight[0];
                const d = flight[1];
                const p = flight[2];

                if (prices[s] === Number.MAX_SAFE_INTEGER) continue;

                if (prices[s] + p < tmpPrices[d]) tmpPrices[d] = prices[s] + p;
            }

            prices = tmpPrices;
        }

        return prices[dst] === Number.MAX_SAFE_INTEGER ? -1 : prices[dst];
    }
}

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] prices = new int[n];
        Array.Fill(prices, int.MaxValue);
        prices[src] = 0;

        for (int i = 0; i <= k; i++) {
            int[] tmpPrices = (int[])prices.Clone();

            foreach (var flight in flights) {
                int s = flight[0];
                int d = flight[1];
                int p = flight[2];

                if (prices[s] == int.MaxValue)
                    continue;

                if (prices[s] + p < tmpPrices[d])
                    tmpPrices[d] = prices[s] + p;
            }

            prices = tmpPrices;
        }

        return prices[dst] == int.MaxValue ? -1 : prices[dst];
    }
}

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    prices := make([]int, n)
    for i := range prices {
        prices[i] = math.MaxInt32
    }
    prices[src] = 0

    for i := 0; i <= k; i++ {
        tmpPrices := make([]int, n)
        copy(tmpPrices, prices)

        for _, flight := range flights {
            s, d, p := flight[0], flight[1], flight[2]
            if prices[s] == math.MaxInt32 {
                continue
            }
            if prices[s] + p < tmpPrices[d] {
                tmpPrices[d] = prices[s] + p
            }
        }
        prices = tmpPrices
    }

    if prices[dst] == math.MaxInt32 {
        return -1
    }
    return prices[dst]
}

class Solution {
    fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {
        val prices = IntArray(n) { Int.MAX_VALUE }
        prices[src] = 0

        repeat(k + 1) {
            val tmpPrices = prices.copyOf()
            for ((s, d, p) in flights) {
                if (prices[s] == Int.MAX_VALUE) continue
                if (prices[s] + p < tmpPrices[d]) {
                    tmpPrices[d] = prices[s] + p
                }
            }
            tmpPrices.copyInto(prices)
        }

        return if (prices[dst] == Int.MAX_VALUE) -1 else prices[dst]
    }
}

impl Solution {
    pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
        let n = n as usize;
        let mut prices = vec![i32::MAX; n];
        prices[src as usize] = 0;

        for _ in 0..=k {
            let mut tmp_prices = prices.clone();
            for flight in &flights {
                let (s, d, p) = (flight[0] as usize, flight[1] as usize, flight[2]);
                if prices[s] == i32::MAX {
                    continue;
                }
                if prices[s] + p < tmp_prices[d] {
                    tmp_prices[d] = prices[s] + p;
                }
            }
            prices = tmp_prices;
        }

        if prices[dst as usize] == i32::MAX { -1 } else { prices[dst as usize] }
    }
}

Time & Space Complexity

Time complexity: $O(n + (m * k))$
Space complexity: $O(n)$

Where $n$ is the number of cities, $m$ is the number of flights and $k$ is the number of stops.

3. Shortest Path Faster Algorithm

Intuition

This problem is still about finding the cheapest path with at most k stops.
SPFA (Shortest Path Faster Algorithm) is essentially a queue-optimized Bellman–Ford.

Key observations:

Each time we relax an edge, we may improve the cost to reach a city.
However, unlike classic shortest path problems, we must not exceed k stops.
So every state in the queue must track:
- the current city
- the total cost so far
- the number of stops used
We only continue expanding a path if stops <= k.

This approach works well because:

Only promising states (those that improve cost) are pushed into the queue.
The stop constraint naturally prevents infinite relaxation loops.

Algorithm

Initialize:
- prices[i] = infinity for all cities.
- prices[src] = 0.
Build an adjacency list from the flight data.
Use a queue that stores (currentCost, city, stopsUsed).
- Start with (0, src, 0).
While the queue is not empty:
- Pop a state (cost, node, stops).
- If stops > k, skip it.
- For each outgoing flight (node -> neighbor, price):
  - Compute nextCost = cost + price.
  - If nextCost < prices[neighbor]:
    - Update prices[neighbor].
    - Push (nextCost, neighbor, stops + 1) into the queue.
After processing:
- If prices[dst] is still infinity, return -1.
- Otherwise, return prices[dst].

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        prices = [float("inf")] * n
        prices[src] = 0
        adj = [[] for _ in range(n)]
        for u, v, cst in flights:
            adj[u].append([v, cst])

        q = deque([(0, src, 0)])
        while q:
            cst, node, stops = q.popleft()
            if stops > k:
                continue

            for nei, w in adj[node]:
                nextCost = cst + w
                if nextCost < prices[nei]:
                    prices[nei] = nextCost
                    q.append((nextCost, nei, stops + 1))

        return prices[dst] if prices[dst] != float("inf") else -1

public class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] prices = new int[n];
        Arrays.fill(prices, Integer.MAX_VALUE);
        prices[src] = 0;
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (var flight : flights) {
            adj[flight[0]].add(new int[] { flight[1], flight[2] });
        }

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { 0, src, 0 });

        while (!q.isEmpty()) {
            var curr = q.poll();
            int cst = curr[0], node = curr[1], stops = curr[2];
            if (stops > k) continue;

            for (var neighbor : adj[node]) {
                int nei = neighbor[0], w = neighbor[1];
                int nextCost = cst + w;
                if (nextCost < prices[nei]) {
                    prices[nei] = nextCost;
                    q.offer(new int[] { nextCost, nei, stops + 1 });
                }
            }
        }
        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> prices(n, INT_MAX);
        prices[src] = 0;
        vector<vector<pair<int, int>>> adj(n);
        for (const auto& flight : flights) {
            adj[flight[0]].emplace_back(flight[1], flight[2]);
        }

        queue<tuple<int, int, int>> q;
        q.push({0, src, 0});

        while (!q.empty()) {
            auto [cst, node, stops] = q.front();
            q.pop();
            if (stops > k) continue;

            for (const auto& neighbor : adj[node]) {
                int nei = neighbor.first, w = neighbor.second;
                int nextCost = cst + w;
                if (nextCost < prices[nei]) {
                    prices[nei] = nextCost;
                    q.push({nextCost, nei, stops + 1});
                }
            }
        }
        return prices[dst] == INT_MAX ? -1 : prices[dst];
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number[][]} flights
     * @param {number} src
     * @param {number} dst
     * @param {number} k
     * @return {number}
     */
    findCheapestPrice(n, flights, src, dst, k) {
        const prices = Array(n).fill(Infinity);
        prices[src] = 0;
        const adj = Array.from({ length: n }, () => []);

        for (const [u, v, cst] of flights) {
            adj[u].push([v, cst]);
        }

        const q = new Queue([[0, src, 0]]); // [cost, node, stops]

        while (!q.isEmpty()) {
            const [cst, node, stops] = q.pop();
            if (stops > k) continue;

            for (const [nei, w] of adj[node]) {
                const nextCost = cst + w;
                if (nextCost < prices[nei]) {
                    prices[nei] = nextCost;
                    q.push([nextCost, nei, stops + 1]);
                }
            }
        }
        return prices[dst] === Infinity ? -1 : prices[dst];
    }
}

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] prices = new int[n];
        Array.Fill(prices, int.MaxValue);
        prices[src] = 0;
        List<int[]>[] adj = new List<int[]>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int[]>();
        }
        foreach (var flight in flights) {
            adj[flight[0]].Add(new int[] { flight[1], flight[2] });
        }

        var q = new Queue<(int cst, int node, int stops)>();
        q.Enqueue((0, src, 0));

        while (q.Count > 0) {
            var (cst, node, stops) = q.Dequeue();
            if (stops > k) continue;

            foreach (var neighbor in adj[node]) {
                int nei = neighbor[0], w = neighbor[1];
                int nextCost = cst + w;
                if (nextCost < prices[nei]) {
                    prices[nei] = nextCost;
                    q.Enqueue((nextCost, nei, stops + 1));
                }
            }
        }
        return prices[dst] == int.MaxValue ? -1 : prices[dst];
    }
}

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    prices := make([]int, n)
    for i := range prices {
        prices[i] = math.MaxInt32
    }
    prices[src] = 0

    adj := make([][][2]int, n)
    for _, flight := range flights {
        from, to, cost := flight[0], flight[1], flight[2]
        adj[from] = append(adj[from], [2]int{to, cost})
    }

    q := [][3]int{{0, src, 0}}

    for len(q) > 0 {
        curr := q[0]
        q = q[1:]
        cst, node, stops := curr[0], curr[1], curr[2]

        if stops > k {
            continue
        }

        for _, neighbor := range adj[node] {
            nei, w := neighbor[0], neighbor[1]
            nextCost := cst + w
            if nextCost < prices[nei] {
                prices[nei] = nextCost
                q = append(q, [3]int{nextCost, nei, stops + 1})
            }
        }
    }

    if prices[dst] == math.MaxInt32 {
        return -1
    }
    return prices[dst]
}

class Solution {
    fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {
        val prices = IntArray(n) { Int.MAX_VALUE }
        prices[src] = 0

        val adj = Array(n) { mutableListOf<Pair<Int, Int>>() }
        for (flight in flights) {
            val (from, to, cost) = flight
            adj[from].add(Pair(to, cost))
        }

        val q: Queue<Triple<Int, Int, Int>> = LinkedList()
        q.offer(Triple(0, src, 0))

        while (q.isNotEmpty()) {
            val (cst, node, stops) = q.poll()
            if (stops > k) continue

            for ((nei, w) in adj[node]) {
                val nextCost = cst + w
                if (nextCost < prices[nei]) {
                    prices[nei] = nextCost
                    q.offer(Triple(nextCost, nei, stops + 1))
                }
            }
        }

        return if (prices[dst] == Int.MAX_VALUE) -1 else prices[dst]
    }
}

impl Solution {
    pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
        let n = n as usize;
        let mut prices = vec![i32::MAX; n];
        prices[src as usize] = 0;
        let mut adj = vec![vec![]; n];
        for flight in &flights {
            adj[flight[0] as usize].push((flight[1] as usize, flight[2]));
        }

        let mut q = VecDeque::new();
        q.push_back((0i32, src as usize, 0i32));

        while let Some((cst, node, stops)) = q.pop_front() {
            if stops > k {
                continue;
            }
            for &(nei, w) in &adj[node] {
                let next_cost = cst + w;
                if next_cost < prices[nei] {
                    prices[nei] = next_cost;
                    q.push_back((next_cost, nei, stops + 1));
                }
            }
        }

        if prices[dst as usize] == i32::MAX { -1 } else { prices[dst as usize] }
    }
}

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(n + m)$

Where $n$ is the number of cities, $m$ is the number of flights and $k$ is the number of stops.

Common Pitfalls

Confusing Stops vs Flights (Off-by-One)

The problem allows at most k stops, which means at most k+1 flights. A common mistake is running Bellman-Ford for k iterations instead of k+1, or checking stops > k when you should check stops == k before taking another flight.

# Wrong: only k iterations (k flights, not k+1)
for i in range(k):
# Correct: k+1 iterations for k stops
for i in range(k + 1):

Not Using a Temporary Array in Bellman-Ford

When relaxing edges, using the same array for both reading and writing allows paths from the current iteration to chain together, potentially exceeding the allowed number of flights in a single round.

# Wrong: updates affect same iteration
if prices[s] + p < prices[d]:
    prices[d] = prices[s] + p
# Correct: use temporary array
if prices[s] + p < tmpPrices[d]:
    tmpPrices[d] = prices[s] + p

Using Standard Dijkstra Without Stop Tracking

Standard Dijkstra finds the cheapest path but ignores the stop constraint. A path with fewer stops might be more expensive but still valid, while the cheapest path might exceed k stops. The state must include both cost and number of stops used.

# Wrong: only tracks cost
dist[city] = cost
# Correct: track cost at each stop level
dist[city][stops] = cost