20. Cheapest Flights Within K Stops

There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.

Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -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 graph looks like this:


The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Solution : (Dijkstra Algorithm)

The key difference with the classic Dijkstra algo is, we don't maintain the global optimal distance to each node.

Because there could be routes which their length is shorter but pass more stops, and those routes don't necessarily constitute the best route in the end. To deal with this, rather than maintain the optimal routes with 0..K stops for each node, the solution simply put all possible routes into the priority queue, so that all of them has a chance to be processed.

class Solution
{
public:
    int findSortestPath(vector<pair<int, int>> v[], int src, int dst, int K)
    {
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
        pq.push({0, {src, K}});

        while (!pq.empty())
        {
            int node = pq.top().second.first;
            int stops = pq.top().second.second;
            int price = pq.top().first;
            pq.pop();
            if (node == dst)
            {
                return price;
            }

            if (stops >= 0)
            {
                for (auto itr = v[node].begin(); itr != v[node].end(); itr++)
                {
                    int x = (*itr).first;
                    int w = (*itr).second;
                    pq.push({price + w, {x, stops - 1}});
                }
            }
        }
        return -1;
    }

    int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int K)
    {

        vector<pair<int, int>> v[n];

        for (int i = 0; i < flights.size(); i++)
        {
            v[flights[i][0]].push_back({flights[i][1], flights[i][2]});
        }

        int price = findSortestPath(v, src, dst, K);

        return price;
    }
};

Time Complexity: O(V + E log V)