787. Cheapest Flights Within K Stops - Detailed Explanation

Problem Statement

You are given n cities numbered 0 to n−1 and a list of flights where each flight is represented as [u, v, w] meaning there is a flight from city u to city v with cost w. You want to travel from source city src to destination city dst with at most K stops (i.e., up to K+1 edges). Return the minimum cost of such a trip; if it’s impossible within K stops, return -1.

Examples

Example 1

Input

n = 3  
flights = [[0,1,100],[1,2,100],[0,2,500]]  
src = 0, dst = 2, K = 1  

Output

200  

Explanation
0→1→2 costs 100+100 = 200 with 1 stop.

Example 2

Input

n = 3  
flights = [[0,1,100],[1,2,100],[0,2,500]]  
src = 0, dst = 2, K = 0  

Output

500  

Explanation
Direct flight 0→2 costs 500 with 0 stops.

Example 3

Input

n = 4  
flights = [[0,1,100],[1,2,100],[2,3,100],[0,3,500]]  
src = 0, dst = 3, K = 1  

Output

500  

Explanation
Any route via an intermediate city uses ≥2 stops, so only direct flight is valid.

Constraints

• 1 ≤ n ≤ 100
• 0 ≤ flights.length ≤ n·(n−1)
• Each flight cost 0 ≤ w ≤ 10⁴
• 0 ≤ src, dst < n
• 0 ≤ K < n

Approach 1 – Bellman‑Ford‑Style DP

Idea

Treat each allowed stop as one relaxation round. Maintain an array dist[] of size n where dist[i] is the cheapest cost to reach i using at most the current number of stops. Initialize dist[src] = 0 and others = ∞. For up to K+1 rounds, create a new array tmp = dist[:] and for each flight u→v with cost w do

tmp[v] = min(tmp[v], dist[u] + w)

Then copy tmp back into dist. After K+1 rounds, dist[dst] is the answer or ∞.

Step‑by‑step

1. Initialize dist = [0,∞,∞,…]
2. Round 1: relax all edges once → cheapest using ≤0 stops (just direct edges)
3. Round 2: relax again → cheapest using ≤1 stop
   …
4. After K+1 rounds, we have allowed K stops.

Approach 2 – Modified Dijkstra with Stop Count

Idea

Use a min‑heap storing tuples (cost, city, stopsUsed). Always expand the current cheapest path, but only push neighbors if stopsUsed ≤ K. Keep a record of best (city, stopsUsed) seen to prune.

Outline

1. Push (0, src, 0) into heap
2. While heap not empty: pop (cost, u, stops)
3. If u == dst, return cost
4. If stops > K, continue
5. For each neighbor v of u with price w: if this path to v with stops+1 is better than any seen before, push (cost+w, v, stops+1).
6. If no return by end, return -1.

Approach 3 – BFS Level by Level

Idea

Perform BFS from src, where each level represents one additional stop. Keep a queue of (city, cost). At each level up to K+1, process all nodes in queue, relax their outgoing flights, and build the next‑level queue with updated costs, always tracking the minimum cost seen for each city to avoid revisiting more expensive paths.

Python Implementation