Problem Overview

You are given:

• An integer n representing the number of cities (from 0 to n - 1).
• A list of flights, where each flight is represented as [from, to, price].
• Two integers src (starting city) and dst (destination city).
• An integer k, representing the maximum number of stops allowed between src and dst.

Your task is to find the cheapest price to travel from src to dst with at most k stops.
If there is no such route, return -1.

---

Example 1

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:
The direct flight 0 → 3 costs 500.
The cheapest route with at most 1 stop is 0 → 1 → 2 → 3, but it has 2 stops, so it's invalid.

---

Example 2

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 200 and has 1 stop.

---

Intuition

This problem can be viewed as finding the shortest path in a weighted directed graph with an additional constraint on the number of stops.
You must find the minimum cost route where the number of edges (flights) used ≤ k + 1.

Unlike standard Dijkstra’s algorithm, where we only care about minimum distance,
here we must also track how many stops we have made so far.

Thus, we can use a modified BFS or Dijkstra-like approach that keeps track of:

1. Current city
2. Total cost so far
3. Number of stops made

---

Approach: BFS (Modified Dijkstra’s)

Idea

We use a priority queue (min-heap) to always expand the cheapest route first,
and maintain a stops counter for each node.

At each step, we:

1. Pop the current state (cost, city, stops) from the heap.
2. If city == dst, return the cost.
3. If stops > k, continue (exceeds limit).
4. For each neighbor (nextCity, nextCost), push (cost + nextCost, nextCity, stops + 1) into the heap.

If we never reach the destination within k stops, return -1.

---

Algorithm Steps

1. Build an adjacency list from the flight data:
   For each [from, to, price], store (to, price) in the adjacency list.
2. Use a priority queue storing {totalCost, city, stops}.
3. Initialize the heap with {0, src, 0}.
4. Maintain a costs array to record the minimum cost to reach a city with a certain number of stops.
5. While the queue is not empty:
   • Pop the current node.
   • If the destination is reached, return cost.
   • If the number of stops > k, skip.
   • For each neighbor, if the new cost is cheaper, add it to the queue.
6. If the queue becomes empty and destination is not reached, return -1.

---

Example Walkthrough

Input:

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

Adjacency list:

0 → [(1,100), (2,500)]
1 → [(2,100)]

Priority Queue initially: [(0, 0, 0)]
→ cost = 0, city = 0, stops = 0

Step 1: Pop (0, 0, 0)
→ Push (100, 1, 1) and (500, 2, 1)

Step 2: Pop (100, 1, 1)
→ Push (200, 2, 2)

Step 3: Pop (200, 2, 2)
→ Destination found → return 200.

---

Java Code Implementation

import java.util.*;

public class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        
        // Build adjacency list
        for (int[] flight : flights) {
            graph.computeIfAbsent(flight[0], x -> new ArrayList<>()).add(new int[]{flight[1], flight[2]});
        }

        // Min-heap based on cost
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, src, 0}); // cost, city, stops

        // Store best [city, stops] combination cost
        int[][] best = new int[n][k + 2];
        for (int[] row : best) Arrays.fill(row, Integer.MAX_VALUE);
        best[src][0] = 0;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int cost = curr[0], city = curr[1], stops = curr[2];

            if (city == dst) return cost;
            if (stops > k) continue;

            if (!graph.containsKey(city)) continue;

            for (int[] neighbor : graph.get(city)) {
                int nextCity = neighbor[0];
                int nextCost = neighbor[1];
                int totalCost = cost + nextCost;

                if (totalCost < best[nextCity][stops + 1]) {
                    best[nextCity][stops + 1] = totalCost;
                    pq.offer(new int[]{totalCost, nextCity, stops + 1});
                }
            }
        }
        return -1;
    }
}

---

Complexity Analysis

Aspect	Analysis
Time Complexity	O(E log V) — Each flight (edge) can be processed up to k + 1 times
Space Complexity	O(V × K) for the best matrix and adjacency list

---

Alternative Approaches

1. Bellman-Ford Variant
   • Relax all edges up to k + 1 times.
   • Time complexity: O(k × E)
   • Easier to implement but slower for dense graphs.
2. DFS with Memoization
   • Use recursion and cache (city, stops) → cost.
   • May cause stack overflow on large input; less efficient.

---

Key Takeaways

1. This is a shortest-path problem with a constraint on the number of edges.
2. A simple Dijkstra’s algorithm fails because it doesn’t handle “stops” limitation.
3. Modified BFS or Dijkstra (priority queue + stops tracking) is efficient.
4. Bellman-Ford works well for smaller datasets or simple implementation needs.