2023-01-26 Daily Challenge
Today I have done leetcode's January LeetCoding Challenge with cpp
.
January LeetCoding Challenge 26
Description
Cheapest Flights Within K Stops
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
Solution
class Solution {
using pi = pair<int, int>;
vector<vector<pi>> neighbors;
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
neighbors.resize(n);
for(const auto &flight : flights) {
neighbors[flight[0]].push_back({flight[1], flight[2]});
}
vector<int> costs(n, INT_MAX);
queue<pi> q;
q.push({0, src});
k += 1; // k stops means path contains at most k + 2 cities
while(q.size() && k--) {
int sz = q.size();
// cout << k << ':' << sz << endl;
for(int _ = 0; _ < sz; ++_) {
auto [cost, current] = q.front();
q.pop();
for(const auto &[next, price] : neighbors[current]) {
if(cost + price >= costs[next]) continue;
costs[next] = cost + price;
q.push({cost + price, next});
}
}
}
return costs[dst] == INT_MAX ? -1 : costs[dst];
}
};
// Accepted
// 52/52 cases passed (32 ms)
// Your runtime beats 59.58 % of cpp submissions
// Your memory usage beats 75.69 % of cpp submissions (13.1 MB)