commit 7fa2da482a8f351409139789b98197777e975abb
parent 266062a9f845d6a749a20df28d6acb8993ce686f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Thu, 5 Jan 2023 17:22:53 +0100
Finish Medium Graph Problems
Diffstat:
7 files changed, 181 insertions(+), 0 deletions(-)
diff --git a/Problems/0787.cpp b/Problems/0787.cpp
@@ -0,0 +1,31 @@
+class Solution {
+ struct edge {
+ int d, w, s;
+ edge(int d, int w, int s = -1) : d(d), w(w), s(s) {}
+ friend bool operator<(const edge &e1, const edge &e2) {
+ return e1.w > e2.w;
+ }
+ };
+
+public:
+ int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst,
+ int k) {
+ vector<vector<edge>> adj(n);
+ for (auto &f : flights) adj[f[0]].push_back({f[1], f[2]});
+
+ vector<int> stop(n, INT_MAX);
+ priority_queue<edge> pq;
+
+ pq.push({src, 0, 0});
+ while (!pq.empty()) {
+ auto [d, w, s] = pq.top();
+ pq.pop();
+ if (s > stop[d] || s > k + 1) continue;
+
+ stop[d] = s;
+ if (d == dst) return w;
+ for (auto [d1, w1, _] : adj[d]) pq.push({d1, w + w1, s + 1});
+ }
+ return -1;
+ }
+};
diff --git a/Problems/1042.cpp b/Problems/1042.cpp
@@ -0,0 +1,24 @@
+class Solution {
+public:
+ vector<int> gardenNoAdj(int n, vector<vector<int>> &paths) {
+ vector<vector<int>> adj(n);
+ for (auto &p : paths) {
+ adj[p[0] - 1].push_back(p[1] - 1);
+ adj[p[1] - 1].push_back(p[0] - 1);
+ }
+
+ vector<int> res(n);
+ for (int i = 0; i < n; i++) {
+ bitset<5> colors;
+
+ for (int c : adj[i]) colors.set(res[c]);
+
+ for (int j = 1; j < 5; j++) {
+ if (colors[j]) continue;
+ res[i] = j;
+ break;
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/1129.cpp b/Problems/1129.cpp
@@ -0,0 +1,35 @@
+class Solution {
+ typedef vector<vector<int>> ADJ;
+
+public:
+ vector<int> shortestAlternatingPaths(int n, vector<vector<int>> &redEdges,
+ vector<vector<int>> &blueEdges) {
+ vector<vector<int>> dist(2, vector<int>(n, INT_MAX));
+ vector<ADJ> adj(2, ADJ(n));
+ queue<pair<int, int>> q;
+
+ for (auto &e : redEdges) adj[0][e[0]].push_back(e[1]);
+ for (auto &e : blueEdges) adj[1][e[0]].push_back(e[1]);
+
+ q.push({0, 0});
+ q.push({0, 1});
+ dist[0][0] = dist[1][0] = 0;
+ while (!q.empty()) {
+ auto [crnt, col] = q.front();
+ q.pop();
+ for (int c : adj[!col][crnt]) {
+ if (dist[!col][c] != INT_MAX) continue;
+ dist[!col][c] = dist[col][crnt] + 1;
+ q.push({c, !col});
+ }
+ }
+
+ vector<int> res(n);
+ for (int i = 0; i < n; i++) {
+ res[i] = min(dist[0][i], dist[1][i]);
+ if (res[i] == INT_MAX) res[i] = -1;
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1976.cpp b/Problems/1976.cpp
@@ -0,0 +1,36 @@
+class Solution {
+ const int MOD = 1e9 + 7;
+ typedef pair<long long, int> road;
+
+public:
+ int countPaths(int n, vector<vector<int>> &roads) {
+ vector<vector<road>> adj(n);
+ for (auto &r : roads) {
+ adj[r[0]].push_back({r[2], r[1]});
+ adj[r[1]].push_back({r[2], r[0]});
+ }
+
+ priority_queue<road, vector<road>, greater<road>> pq;
+ vector<long long> dist(n, LONG_MAX);
+ vector<int> count(n);
+ pq.push({0, 0});
+ count[0] = 1;
+ dist[0] = 0;
+ while (!pq.empty()) {
+ auto [w, e] = pq.top();
+ pq.pop();
+ if (w > dist[e]) continue;
+ for (auto [time, v] : adj[e]) {
+ if (dist[v] < w + time) continue;
+ if (dist[v] == w + time) {
+ count[v] = (count[v] + count[e]) % MOD;
+ continue;
+ }
+ dist[v] = w + time;
+ count[v] = count[e];
+ pq.push({dist[v], v});
+ }
+ }
+ return count[n - 1];
+ }
+};
diff --git a/Problems/2359.cpp b/Problems/2359.cpp
@@ -0,0 +1,24 @@
+class Solution {
+public:
+ int closestMeetingNode(vector<int> &e, int node1, int node2) {
+ const int n = e.size();
+ vector<int> d(n, -1);
+
+ for (int i = node1, di = 0; i != -1 && d[i] == -1; i = e[i]) d[i] = di++;
+
+ int res = -1, mini = INT_MAX;
+ for (int i = node2, di = 0; i != -1 && d[i] != -2; i = e[i], di++) {
+ int t = max(d[i], di);
+ if (d[i] != -1 && t <= mini) {
+ if (t < mini)
+ res = i;
+ else
+ res = min(res, i);
+ mini = t;
+ }
+ d[i] = -2;
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/2497.cpp b/Problems/2497.cpp
@@ -0,0 +1,25 @@
+class Solution {
+public:
+ int maxStarSum(vector<int> &vals, vector<vector<int>> &edges, int k) {
+ vector<vector<int>> adj(vals.size());
+
+ for (auto &e : edges) {
+ adj[e[0]].push_back(e[1]);
+ adj[e[1]].push_back(e[0]);
+ }
+
+ int res = INT_MIN;
+ for (int i = 0; i < vals.size(); i++) {
+ priority_queue<int, vector<int>, greater<int>> pq;
+ for (int c : adj[i]) {
+ if (vals[c] <= 0) continue;
+ pq.push(vals[c]);
+ if (pq.size() > k) pq.pop();
+ }
+ int sum = vals[i];
+ while (!pq.empty()) sum += pq.top(), pq.pop();
+ res = max(res, sum);
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -181,6 +181,7 @@ for solving problems.
| 0752 | Medium | [Open the Lock](Problems/0752.cpp) |
| 0783 | Easy | [Minimum Distance Between BST Nodes](Problems/0783.cpp) |
| 0785 | Medium | [Is Graph Bipartite?](Problems/0785.cpp) |
+| 0787 | Medium | [Cheapest Flights Within K Stops](Problems/0787.cpp) |
| 0797 | Medium | [All Paths From Source to Target](Problems/0797.cpp) |
| 0802 | Medium | [Find Eventual Safe States](Problems/0802.cpp) |
| 0830 | Medium | [Kth Smallest Element in a BST](Problems/0230.cpp) |
@@ -213,11 +214,13 @@ for solving problems.
| 1022 | Easy | [Sum of Root To Leaf Binary Numbers](Problems/1022.cpp) |
| 1026 | Medium | [Maximum Difference Between Node and Ancestor](Problems/1026.cpp) |
| 1038 | Medium | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp) |
+| 1042 | Medium | [Flower Planting With No Adjacent](Problems/1042.cpp) |
| 1047 | Easy | [Remove All Adjacent Duplicates In String](Problems/1047.cpp) |
| 1051 | Easy | [Height Checker](Problems/1051.cpp) |
| 1089 | Easy | [Duplicate Zeros](Problems/1089.cpp) |
| 1095 | Easy | [Find Numbers with Even Number of Digits](Problems/1095.cpp) |
| 1099 | Easy | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp) |
+| 1129 | Medium | [Shortest Path with Alternating Colors](Problems/1129.cpp) |
| 1137 | Easy | [N-th Tribonacci Number](Problems/1137.cpp) |
| 1202 | Medium | [Smallest String With Swaps](Problems/1202.cpp) |
| 1209 | Medium | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp) |
@@ -265,6 +268,7 @@ for solving problems.
| 1926 | Medium | [Nearest Exit from Entrance in Maze](Problems/1926.cpp) |
| 1962 | Medium | [Remove Stones to Minimize the Total](Problems/1962.cpp) |
| 1971 | Easy | [Find if Path Exists in Graph](Problems/1971.cpp) |
+| 1976 | Medium | [Number of Ways to Arrive at Destination](Problems/1976.cpp) |
| 2039 | Medium | [The Time When the Network Becomes Idle](Problems/2039.cpp) |
| 2073 | Easy | [Time Needed to Buy Tickets](Problems/2073.cpp) |
| 2095 | Medium | [Delete the Middle Node of a Linked List](Problems/2095.cpp) |
@@ -283,6 +287,7 @@ for solving problems.
| 2316 | Medium | [Count Unreachable Pairs of Nodes in an Undirected Graph](Problems/2316.cpp) |
| 2326 | Medium | [Spiral Matrix IV](Problems/2326.cpp) |
| 2331 | Easy | [Evaluate Boolean Binary Tree](Problems/2331.cpp) |
+| 2359 | Medium | [Find Closest Node to Given Two Nodes](Problems/2359.cpp) |
| 2368 | Medium | [Reachable Nodes With Restrictions](Problems/2368.cpp) |
| 2374 | Medium | [Node With Highest Edge Score](Problems/2374.cpp) |
| 2390 | Medium | [Removing Stars From a String](Problems/2390.cpp) |
@@ -292,4 +297,5 @@ for solving problems.
| 2467 | Medium | [Most Profitable Path in a Tree](Problems/2467.cpp) |
| 2477 | Medium | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp) |
| 2492 | Medium | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp) |
+| 2497 | Medium | [Maximum Star Sum of a Graph](Problems/2497.cpp) |
