Problem Statement

There are n cities and m edges connected by some number of flights. Given an array of flights where flights[i] = [ fromi, toi, pricei] indicates that there is a flight from city from i to city to with cost price. Given three integers src, dst, and k, and 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 optimal path with at most 1 stops from city 0 to 3 is 0->1->3 has cost 100 + 600 = 700.
Note: The path through cities 0->1->2->3 is cheaper but invalid as it used 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 optimal path with at most 1 stops from city 0 to 2 is 0->1->2 and has cost 100 + 100 = 200.

Different Approaches

1️⃣ Modified Dijkstra Algorithm

Code:

Using Tuple

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // Build the adjacency list: each city u has pairs {v, price}
        vector<vector<pair<int, int>>> adj(n);
        for (const auto &flight : flights) {
            int u = flight[0], v = flight[1], price = flight[2];
            adj[u].push_back({v, price});
        }
        
        // Priority queue (min-heap) to store states: (cost, current city, stops taken)
        priority_queue<
            tuple<int, int, int>,
            vector<tuple<int, int, int>>,
            greater<tuple<int, int, int>>
        > pq;
        
        // Start from src with cost = 0 and 0 stops.
        pq.push({0, src, 0});
        
        // Process the queue
        while (!pq.empty()) {
            auto [cost, city, stops] = pq.top();
            pq.pop();
            
            // If we reached the destination, return the cost
            if (city == dst) {
                return cost;
            }
            
            // If the current number of stops is within the allowed limit,
            // explore the neighbors.
            if (stops <= k) {
                for (auto [nextCity, price] : adj[city]) {
                    pq.push({cost + price, nextCity, stops + 1});
                }
            }
        }
        
        // If destination is not reachable within k stops, return -1
        return -1;
    }
};

Using Pair

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // Build the adjacency list: for each city, store pairs of (neighbor, price)
        vector<vector<pair<int, int>>> adj(n);
        for (const auto &flight : flights) {
            int u = flight[0], v = flight[1], price = flight[2];
            adj[u].push_back({v, price});
        }
        
        // Priority queue (min-heap) using pair:
        // state: (total cost, (current city, stops so far))
        priority_queue<
            pair<int, pair<int, int>>,
            vector<pair<int, pair<int, int>>>,
            greater<pair<int, pair<int, int>>>
        > pq;
        
        // Start from src with cost = 0 and 0 stops.
        pq.push({0, {src, 0}});
        
        while (!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            
            int cost = top.first;
            int city = top.second.first;
            int stops = top.second.second;
            
            // If we've reached the destination, return the cost.
            if (city == dst)
                return cost;
            
            // Only proceed if we haven't exceeded the allowed stops.
            if (stops < k) {
                for (const auto &edge : adj[city]) {
                    int nextCity = edge.first;
                    int price = edge.second;
                    pq.push({cost + price, {nextCity, stops + 1}});
                }
            }
        }
        
        // If destination cannot be reached within k stops, return -1.
        return -1;
    }
};

Complexity Analysis:

• Time Complexity:
  • Graph Construction:
    • Converting the flights into an adjacency list takes O(m), where m is the number of fligts.
  • State Processing:
    • In the worst case, each city may be pushed into the priority queue with different stops counts. The maximum number of states is approximately O(n*(k+1)). Each push/pop operation from the priority queue takes O(log(n*(k+1))).
  • Overall:
    • O(m+n * (k + 1) log (n*(k+1)))
• Space Complexity:
  • Adjacency List:
    • O(n + m)
  • Priority Queue:
    • In the worst case, holds up to O(n * (k + 1)) states
  • Overall:
    • O(n * (k + 1) + m)