> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/graph/19.-cheapest-flights-within-k-stops.md).

# 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`.

![](/files/-MPwS_JHRKo30LCCBhwb)

```
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.

```cpp
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)**