There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Examples

Example 1:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 has cost 500.

Constraints

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= fromi, toi < n
  • fromi != toi
  • 1 <= pricei <= 104
  • There will not be any multiple flights between two cities.
  • 0 <= src, dst < n
  • src != dst
  • 0 <= k < n

Thinking Process

  1. Stop Constraint: k stops means at most k+1 edges (k intermediate cities + destination)
  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Solution

from collections import deque

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        adj = [[] for _ in range(n)]
        
        for e in flights:
            adj[e[0]].append((e[1], e[2]))
        
        INF = float('inf')
        prices = [INF] * n
        
        q = deque()
        q.append((src, 0))
        
        stop = 0
        
        while stop <= k and q:
            sz = len(q)
            
            for _ in range(sz):
                node, price = q.popleft()
                
                for neighbor, currPrice in adj[node]:
                    newPrice = price + currPrice
                    
                    if newPrice >= prices[neighbor]:
                        continue
                    
                    prices[neighbor] = newPrice
                    q.append((neighbor, newPrice))
            
            stop += 1
        
        return -1 if prices[dst] == INF else prices[dst]

Solution Explanation

Approach: 1D DP (this problem)

Key idea: 1. Stop Constraint: k stops means at most k+1 edges (k intermediate cities + destination)

How the code works:

  1. Stop Constraint: k stops means at most k+1 edges (k intermediate cities + destination)
    • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
    • Recurrence: how does the answer build from smaller indices?
    • Base cases first; optimize space if only prior row/layer is needed.

Walkthrough — input n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1, expected output 700:

The graph is shown above. The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700. Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Algorithm Breakdown:

  1. Build Adjacency List: Create graph representation
  2. Initialize: Set prices[src] = 0, push (src, 0) to queue
  3. BFS Level-by-Level: For each stop level (0 to k):
    • Process all nodes at current level
    • For each node, explore neighbors and update prices if cheaper
    • Only add to queue if price improved (pruning)
  4. Result: Return prices[dst] or -1 if unreachable

Why This Works:

  • Level-by-Level Processing: Ensures we process all nodes reachable in exactly stop stops before moving to stop+1
  • Price Update: Only update if newPrice < prices[neighbor], ensuring we find the cheapest path
  • Stop Limit: The outer loop while(stop <= k) ensures we don’t exceed k stops

Solution 1 (BFS Level-by-Level):

  • Time Complexity: O(n * m * k) - Process each edge up to k+1 times
  • Space Complexity: O(n + m) - Adjacency list and queue

Solution 2 (Bellman-Ford):

  • Time Complexity: O(k * m) - k+1 iterations, each processing all m edges
  • Space Complexity: O(n) - Distance arrays

Solution 3 (Dijkstra with Stops):

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Stop Constraint: k stops means at most k+1 edges (k intermediate cities + destination)
  2. Bellman-Ford Advantage: Naturally handles edge count constraints - perfect for this problem
  3. BFS Level-by-Level: Ensures we process nodes in order of number of stops
  4. Dijkstra with Stops: Track both distance and stops, skip paths that exceed limit or use more stops
  5. Temporary Array: In Bellman-Ford, using tmp prevents using updated distances in the same iteration

References

Template Reference