diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /cheapest_flight_k_stop.cpp | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'cheapest_flight_k_stop.cpp')
-rw-r--r-- | cheapest_flight_k_stop.cpp | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/cheapest_flight_k_stop.cpp b/cheapest_flight_k_stop.cpp new file mode 100644 index 0000000..ed00b9d --- /dev/null +++ b/cheapest_flight_k_stop.cpp @@ -0,0 +1,46 @@ +// 787. Cheapest Flights Within K Stops +#include "leetcode.h" + +/* + * there are 'n' cities connected by some number of flights. you are given array + * 'flights' where 'flight[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, & k'. return the cheapest price + * from 'src' to 'dst' with at most 'k' stops. if there is no such route, -1 + */ + +typedef tuple<int, int, int> tp; +class Solution { +public: + int findCheapestPrice(int n, vvd(int) & flights, int src, int dst, int k) { + vector<vector<pair<int, int>>> vvp(n); + for (const auto &f : flights) + vvp[f[0]].emplace_back(f[1], f[2]); + priority_queue<tp, vector<tp>, greater<tp>> pqvg; + pqvg.emplace(0, src, k + 1); + while (!pqvg.empty()) { + auto [cost, u, stops] = pqvg.top(); + pqvg.pop(); + if (u == dst) + return cost; + if (!stops) + continue; + for (auto to : vvp[u]) { + auto [v, w] = to; + pqvg.emplace(cost + w, v, stops - 1); + } + } + return -1; + } +}; + +int main() { + Solution obj; + vvd(int) flights1 = { + {0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}}; + vvd(int) flights2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}}; + vvd(int) flights3 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}}; + cout << obj.findCheapestPrice(4, flights1, 0, 3, 1) << endl; // expect: 700 + cout << obj.findCheapestPrice(3, flights2, 0, 2, 1) << endl; // expect: 200 + cout << obj.findCheapestPrice(3, flights3, 0, 2, 0) << endl; // expect: 500 +} |