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

# 787. Cheapest Flights Within K Stops

## Problem Statement

\
There are `n` cities connected by some number of flights. You are given an array `flights` where `flights[i] = [fromi, toi, pricei]` indicates that there is a flight from city `fromi` to city `toi` with cost `pricei`.

You are also given three integers `src`, `dst`, and `k`, return ***the cheapest price** from* `src` *to* `dst` *with at most* `k` *stops.* If there is no such route, return `-1`.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-3drawio.png)

<pre><code><strong>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
</strong><strong>Output: 700
</strong><strong>Explanation:
</strong>The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
</code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-1drawio.png)

<pre><code><strong>Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
</strong><strong>Output: 200
</strong><strong>Explanation:
</strong>The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
</code></pre>

**Example 3:**

![](https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-2drawio.png)

<pre><code><strong>Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
</strong><strong>Output: 500
</strong><strong>Explanation:
</strong>The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
</code></pre>

&#x20;

**Constraints:**

* `1 <= n <= 100`
* `0 <= flights.length <= (n * (n - 1) / 2)`
* `flights[i].length == 3`
* `0 <= fromi, toi < n`
* `fromi != toi`
* `1 <= pricei <= 104`
* There will not be any multiple flights between two cities.
* `0 <= src, dst, k < n`
* `src != dst`

Accepted421.1KSubmissions1.1MAcceptance Rate37.3%

## Intuition

```
Approach:

// Cannot do based on distance, as Some path with more stops can reach 
// node with less weight, but someone with more weight and stops will not reach


// eg      5
//     1 ---  2 
//     \     /  \ 1
//    2  \  / 1  \ 
//        3       4

//        Look here If we want to reach 4, Min disatce with diskstra is 4
//        But with less stops we can reach the 4 taking 6

//        Hence we priorotize on stops, rather than distance
```

### Links

<https://leetcode.com/problems/cheapest-flights-within-k-stops/description/>

### Video Links

<https://www.youtube.com/watch?v=9XybHVqTHcQ&ab_channel=takeUforward>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // Stops, node, distance
        queue<array<int,3>>q;
        vector<int> dist(n, INT_MAX);

        vector<vector<vector<int>>> adj(n);
        for(auto &it: flights){
            int x = it[0], y = it[1], dist = it[2];
            adj[x].push_back({y, dist});
        }

        dist[src] = 0;
        q.push({0, src, 0});

        while (!q.empty()) {
            array<int,3> arr = q.front();
            int stp = arr[0], node = arr[1], distance = arr[2];
            q.pop();

            if(stp > k)
                continue;

            for(auto &it: adj[node]){
                int neigh = it[0], step = it[1];
                if(distance + step < dist[neigh] and stp<=k){
                    dist[neigh] = step + distance;
                    q.push({stp+1, neigh, dist[neigh]});
                }
            }
        }

        return dist[dst] == INT_MAX ? -1 : dist[dst];
    }
};

```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###