# 787. Cheapest Flights Within K Stops

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

Now given all the cities and fights, 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.

Example 2:
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.
``````

Note:

• The number of nodes `n` will be in range `[1, 100]`, with nodes labeled from `0` to `n`` - 1`.
• The size of `flights` will be in range `[0, n * (n - 1) / 2]`.
• The format of each flight will be `(src, ``dst``, price)`.
• The price of each flight will be in the range `[1, 10000]`.
• `k` is in the range of `[0, n - 1]`.
• There will not be any duplicated flights or self cycles.

``````class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
int res = INT_MAX;
unordered_map<int, vector<vector<int>>> m;
unordered_set<int> visited{{src}};
for (auto flight : flights) {
m[flight[0]].push_back({flight[1], flight[2]});
}
helper(m, src, dst, K, visited, 0, res);
return (res == INT_MAX) ? -1 : res;
}
void helper(unordered_map<int, vector<vector<int>>>& m, int cur, int dst, int K, unordered_set<int>& visited, int out, int& res) {
if (cur == dst) {res = out; return;}
if (K < 0) return;
for (auto a : m[cur]) {
if (visited.count(a[0]) || out + a[1] > res) continue;
visited.insert(a[0]);
helper(m, a[0], dst, K - 1, visited, out + a[1], res);
visited.erase(a[0]);
}
}
};
``````

``````class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
int res = INT_MAX, cnt = 0;
unordered_map<int, vector<vector<int>>> m;
queue<vector<int>> q{{{src, 0}}};
for (auto flight : flights) {
m[flight[0]].push_back({flight[1], flight[2]});
}
while (!q.empty()) {
for (int i = q.size(); i > 0; --i) {
auto t = q.front(); q.pop();
if (t[0] == dst) res = min(res, t[1]);
for (auto a : m[t[0]]) {
if (t[1] + a[1] > res) continue;
q.push({a[0], t[1] + a[1]});
}
}
if (cnt++ > K) break;
}
return (res == INT_MAX) ? -1 : res;
}
};
``````

``````class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
vector<vector<int>> dp(K + 2, vector<int>(n, 1e9));
dp[0][src] = 0;
for (int i = 1; i <= K + 1; ++i) {
dp[i][src] = 0;
for (auto x : flights) {
dp[i][x[1]] = min(dp[i][x[1]], dp[i - 1][x[0]] + x[2]);
}
}
return (dp[K + 1][dst] >= 1e9) ? -1 : dp[K + 1][dst];
}
};
``````

``````class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
vector<int> dp(n, 1e9);
dp[src] = 0;
for (int i = 0; i <= K; ++i) {
vector<int> t = dp;
for (auto x : flights) {
t[x[1]] = min(t[x[1]], dp[x[0]] + x[2]);
}
dp = t;
}
return (dp[dst] >= 1e9) ? -1 : dp[dst];
}
};
``````

Maximum Vacation Days

https://leetcode.com/problems/cheapest-flights-within-k-stops/discuss/115596/c++-8-line-bellman-ford

https://leetcode.com/problems/cheapest-flights-within-k-stops/discuss/128217/Three-C++-solutions-BFS-DFS-and-BF

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation