Cheapest Flights Within K Stops medium

Problem Statement

You are given a graph of n nodes, where each node represents a city. The graph is represented by a 2D array flights where flights[i] = [fromi, toi, pricei] indicates a flight from city fromi to city toi with cost pricei.

You are also given three integers: src (source city), dst (destination city), and k (the maximum number of stops allowed). Find the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1

Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 Output: 200 Explanation: The cheapest price from city 0 to city 2 with at most 1 stop costs 200.

Example 2

Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0 Output: 500 Explanation: The cheapest price from city 0 to city 2 with at most 0 stop costs 500.

Steps

1. Initialization: Create a distance array dist of size n initialized with infinity, except for dist[src] = 0. This array will store the minimum cost to reach each city. Also, create a priority queue pq to store pairs of {cost, {city, stops}}, sorted by cost. Push {0, {src, 0}} into the priority queue.

2. Iteration: While the priority queue is not empty:

   • Pop the element with the minimum cost from the priority queue.
   • If the popped city is the destination, return its cost.
   • Iterate through all flights originating from the popped city:
     • Calculate the cost to reach the destination city of the flight.
     • If this cost is less than the current cost in dist for that destination city and the number of stops is within the limit k, update dist and push the new cost and city information onto the priority queue.

3. No Route Found: If the loop finishes without finding the destination, return -1.

Explanation

This solution utilizes Dijkstra's algorithm with a modification to track the number of stops. The priority queue ensures that we always explore the cheapest paths first, guaranteeing that we find the minimum cost. The stops parameter helps us enforce the constraint of at most k stops. By updating distances only if a cheaper path is found and the stop limit is not exceeded, we efficiently explore the graph.

Code

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // for numeric_limits

using namespace std;

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    vector<long long> dist(n, numeric_limits<long long>::max());
    dist[src] = 0;

    priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>, greater<pair<long long, pair<int, int>>>> pq;
    pq.push({0, {src, 0}});

    while (!pq.empty()) {
        long long cost = pq.top().first;
        int city = pq.top().second.first;
        int stops = pq.top().second.second;
        pq.pop();

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

        for (const auto& flight : flights) {
            if (flight[0] == city) {
                long long newCost = cost + flight[2];
                if (newCost < dist[flight[1]]) {
                    dist[flight[1]] = newCost;
                    pq.push({newCost, {flight[1], stops + 1}});
                }
            }
        }
    }

    return -1;
}

int main() {
    vector<vector<int>> flights = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
    int n = 3, src = 0, dst = 2, k = 1;
    cout << findCheapestPrice(n, flights, src, dst, k) << endl; // Output: 200

    flights = {{0,1,100},{1,2,100},{0,2,500}};
    n = 3; src = 0; dst = 2; k = 0;
    cout << findCheapestPrice(n, flights, src, dst, k) << endl; //Output: 500

    return 0;
}

Complexity

• Time Complexity: O(E log V), where E is the number of flights (edges) and V is the number of cities (vertices). This is due to the priority queue operations.
• Space Complexity: O(V), primarily for the dist array and the priority queue. In the worst case, the priority queue could hold all vertices.