# 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)**


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soumyajit4419.gitbook.io/ds-algo/graph/19.-cheapest-flights-within-k-stops.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.