aboutsummaryrefslogtreecommitdiff
path: root/cheapest_flight_k_stop.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /cheapest_flight_k_stop.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'cheapest_flight_k_stop.cpp')
-rw-r--r--cheapest_flight_k_stop.cpp46
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
+}