# 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:**
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
Output: 700
Explanation:
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.
**Example 2:**
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
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.
**Example 3:**
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
**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
### Video Links
### Approach 1:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
class Solution {
public:
int findCheapestPrice(int n, vector>& flights, int src, int dst, int k) {
// Stops, node, distance
queue>q;
vector dist(n, INT_MAX);
vector>> 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 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
###
---
# 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://coding-9.gitbook.io/untitled/graph/shortest-path/787.-cheapest-flights-within-k-stops.md?ask=
```
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.