leetcode

commit 2fc6ad699580a8e52b5b46eafa3816ecf4391536
parent 2b6b0d00c7816e658165387dd04eb664cd4ddf38
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 30 Aug 2024 21:08:13 +0200

Daily Problem

Diffstat:
A
Problems/2699.cpp
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 62 insertions(+), 0 deletions(-)
diff --git a/Problems/2699.cpp b/Problems/2699.cpp
@@ -0,0 +1,61 @@
+class Solution {
+    using edge_t = pair<int, int>;
+    using adj_t = vector<vector<edge_t>>;
+
+    void dijkstra(const adj_t &adj, vector<vector<int>> &edges, vector<vector<int>> &dist, int src, int diff,
+                  int run) {
+        int n = adj.size();
+        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
+
+        dist[src][run] = 0;
+        pq.emplace(0, src);
+        while (!pq.empty()) {
+            auto [currentdist, currentNode] = pq.top();
+            pq.pop();
+
+            if (currentdist > dist[currentNode][run]) continue;
+            for (auto &[next, idx] : adj[currentNode]) {
+                int w = edges[idx][2];
+
+                if (w == -1) w = 1;
+
+                if (run == 1 && edges[idx][2] == -1) {
+                    int nw = diff + dist[next][0] - dist[currentNode][1];
+                    if (nw > w) {
+                        edges[idx][2] = w = nw;
+                    }
+                }
+
+                if (dist[next][run] > dist[currentNode][run] + w) {
+                    dist[next][run] = dist[currentNode][run] + w;
+                    pq.emplace(dist[next][run], next);
+                }
+            }
+        }
+    }
+
+  public:
+    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>> &edges, int src, int dest, int tgt) {
+        vector<vector<pair<int, int>>> adj(n);
+        for (int i = 0; i < edges.size(); i++) {
+            int a = edges[i][0], b = edges[i][1];
+            adj[a].emplace_back(b, i);
+            adj[b].emplace_back(a, i);
+        }
+
+        vector<vector<int>> dist(n, vector<int>(2, INT_MAX));
+        dist[src][0] = dist[src][1] = 0;
+
+        dijkstra(adj, edges, dist, src, 0, 0);
+        int diff = tgt - dist[dest][0];
+        if (diff < 0) return {};
+
+        dijkstra(adj, edges, dist, src, diff, 1);
+        if (dist[dest][1] < tgt) return {};
+
+        for (auto &edge : edges) {
+            if (edge[2] == -1) edge[2] = 1;
+        }
+        return edges;
+    }
+};
diff --git a/README.md b/README.md
@@ -1265,6 +1265,7 @@ for solving problems.
 |  2683  |   Medium   | [Neighboring Bitwise XOR](Problems/2683.cpp)                                                       |
 |  2685  |   Medium   | [Count the Number of Complete Components](Problems/2685.cpp)                                       |
 |  2698  |   Medium   | [Find the Punishment Number of an Integer](Problems/2698.cpp)                                      |
+|  2699  |    Hard    | [Modify Graph Edge Weights](Problems/2699.cpp)                                                     |
 |  2706  |    Easy    | [Buy Two Chocolates](Problems/2706.cpp)                                                            |
 |  2707  |   Medium   | [Extra Characters in a String](Problems/2707.cpp)                                                  |
 |  2709  |    Hard    | [Greatest Common Divisor Traversal](Problems/2709.cpp)                                             |