aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-29 19:50:30 -0600
committerJack Sangdahl <[email protected]>2024-08-29 19:50:30 -0600
commitaccfdfe3a52d62bee9b2c24dece6f2b613ceeb7c (patch)
treeceaf6bad9cb34fb6f6a6ca3080df3496751bf723
parent7dc61c9997c53be6c50726f2a618df397f9ac09f (diff)
downloadleetcode-accfdfe3a52d62bee9b2c24dece6f2b613ceeb7c.tar.gz
leetcode-accfdfe3a52d62bee9b2c24dece6f2b613ceeb7c.zip
2699. modify graph edge weights
-rw-r--r--modify_graph_edge_weight.cpp91
-rw-r--r--modify_graph_edge_weight.py106
2 files changed, 197 insertions, 0 deletions
diff --git a/modify_graph_edge_weight.cpp b/modify_graph_edge_weight.cpp
new file mode 100644
index 0000000..0656f5e
--- /dev/null
+++ b/modify_graph_edge_weight.cpp
@@ -0,0 +1,91 @@
+// 2699. Modify Graph Edge Weights
+#include "leetcode.h"
+
+/*
+ * you are given an undirected weighted connected graph containing 'n' nodes
+ * labeled from '0' to 'n - 1' and an integer array 'edges' where 'edges[i] =
+ * [ai, bi, wi]' indicates that there is an edge between nodes 'ai' and 'bi'
+ * with weight 'wi'. some edges have a weight of -1 ('wi = -1'), while other
+ * have a positive weight ('wi > 0'). your task is to modify all edges with a
+ * weight of -1 by assigning them positive integer values in the range '[1, 2 *
+ * 10^9]' so that the shortest distance between the nodes 'source' and
+ * 'destination' becomes equal to an integer 'target'. if there are multiple
+ * modifications that make the shortest distance equal to 'target', any of them
+ * are considered correct. return an array containing all edges in any order if
+ * it is possible to make the shortest to equal 'target', or an empty array if
+ * it is not possible
+ */
+
+class Solution {
+ array<int, 2> bfs(vector<vector<array<int, 2>>> &adj,
+ vector<vector<int>> &edges, int source, int destination,
+ int target, bool modify) {
+ priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> pq;
+ vector<int> dist(adj.size(), INT_MAX), mod_id(adj.size(), INT_MAX);
+ pq.push({0, source});
+ dist[source] = 0;
+ while (!pq.empty() && pq.top()[1] != destination) {
+ auto [d, i] = pq.top();
+ pq.pop();
+ if (d != dist[i])
+ continue;
+ for (auto [j, edge_id] : adj[i]) {
+ int w = edges[edge_id][2];
+ if (modify || w != -1)
+ if (dist[j] > d + max(1, w)) {
+ mod_id[j] = w == -1 ? edge_id : mod_id[i];
+ dist[j] = d + max(1, w);
+ pq.push({d + max(1, w), j});
+ }
+ }
+ }
+ return {dist[destination], mod_id[destination]};
+ }
+
+public:
+ vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>> &edges,
+ int source, int destination,
+ int target) {
+ vector<vector<array<int, 2>>> adj(n);
+ for (int i = 0; i < edges.size(); ++i) {
+ adj[edges[i][0]].push_back({edges[i][1], i});
+ adj[edges[i][1]].push_back({edges[i][0], i});
+ }
+ auto [dist, _] = bfs(adj, edges, source, destination, target, false);
+ if (dist < target)
+ return {};
+ while (true) {
+ auto [dist, mod_id] = bfs(adj, edges, source, destination, target, true);
+ if (dist > target)
+ return {};
+ if (dist == target)
+ break;
+ edges[mod_id][2] = 1 + target - dist;
+ }
+ for (auto &e : edges)
+ e[2] = e[2] == -1 ? 1 : e[2];
+ return edges;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd(int) e1 = {{4, 1, -1}, {2, 0, -1}, {0, 3, -1}, {4, 3, -1}},
+ e2 = {{0, 1, -1}, {0, 2, 5}},
+ e3 = {{1, 0, 4}, {1, 2, 3}, {2, 3, 5}, {0, 3, -1}};
+ vvd(int) mge1 = obj.modifiedGraphEdges(5, e1, 0, 1, 5),
+ mge2 = obj.modifiedGraphEdges(3, e2, 0, 2, 6),
+ mge3 = obj.modifiedGraphEdges(4, e3, 0, 2, 6);
+ for (int i = 0; i < mge1.size(); i++)
+ for (int j = 0; j < mge1[0].size(); j++)
+ printf("%d ", mge1[i][j]); // expect: [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
+ printf("\n");
+ for (int i = 0; i < mge2.size(); i++)
+ for (int j = 0; j < mge2[0].size(); j++)
+ printf("%d ", mge2[i][j]); // expect: []
+ printf("\n");
+ for (int i = 0; i < mge3.size(); i++)
+ for (int j = 0; j < mge3[0].size(); j++)
+ printf("%d ", mge3[i][j]); // expect: [[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
+ printf("\n");
+}
diff --git a/modify_graph_edge_weight.py b/modify_graph_edge_weight.py
new file mode 100644
index 0000000..67ab7c8
--- /dev/null
+++ b/modify_graph_edge_weight.py
@@ -0,0 +1,106 @@
+# 2699. Modify Graph Edge Weights
+from collections import defaultdict
+import heapq
+
+"""
+you are given an undirected weighted connected graph containing 'n' nodes
+labeled from '0' to 'n - 1' and an integer array 'edges' where 'edges[i] =
+[ai, bi, wi]' indicates that there is an edge between nodes 'ai' and 'bi'
+with weight 'wi'. some edges have a weight of -1 ('wi = -1'), while other
+have a positive weight ('wi > 0'). your task is to modify all edges with a
+weight of -1 by assigning them positive integer values in the range '[1, 2 *
+10^9]' so that the shortest distance between the nodes 'source' and
+'destination' becomes equal to an integer 'target'. if there are multiple
+modifications that make the shortest distance equal to 'target', any of them
+are considered correct. return an array containing all edges in any order if
+it is possible to make the shortest to equal 'target', or an empty array if
+it is not possible
+"""
+
+
+class Solution(object):
+ def modifiedGraphEdges(self, n, edges, source, destination, target):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :type source: int
+ :type destination: int
+ :type target: int
+ :rtype: List[List[int]]
+ """
+ adj = [[] for _ in range(n)]
+ for u, v, w in edges:
+ adj[u].append([v, w])
+ adj[v].append([u, w])
+
+ def dijkstra(source, adj, skip_neg):
+ pq = [[0, source]]
+ dist = defaultdict(lambda: "inf")
+ dist[source] = 0
+ parent = {}
+ while pq:
+ d, node = heapq.heappop(pq)
+ if d > dist[node]:
+ continue
+ for nei, w in adj[node]:
+ if w == -1:
+ if skip_neg:
+ continue
+ w = 1
+ d2 = d + w
+ if d2 < dist[nei]:
+ dist[nei] = d2
+ parent[nei] = node
+ heapq.heappush(pq, [d2, nei])
+ return dist, parent
+
+ dist_r, parent_r = dijkstra(destination, adj, skip_neg=True)
+ if dist_r.get(source, "inf") < target:
+ return []
+ dist, parent = dijkstra(source, adj, skip_neg=False)
+ if dist[destination] > target:
+ return []
+ path = [destination]
+ while path[-1] != source:
+ path.append(parent[path[-1]])
+ path = path[::-1]
+ edges = {(min(u, v), max(u, v)): w for u, v, w in edges}
+ walked = 0
+ for u, v in zip(path, path[1:]):
+ e = (min(u, v), max(u, v))
+ if edges[e] == -1:
+ edges[e] = max(target - dist_r.get(v, "inf") - walked, 1)
+ if edges[e] > 1:
+ break
+ walked += edges[e]
+ for e, w in edges.items():
+ if w == -1:
+ edges[e] = 2 * (10**9)
+ return [[u, v, w] for (u, v), w in edges.items()]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.modifiedGraphEdges(
+ n=5,
+ edges=[[4, 1, -1], [2, 0, -1], [0, 3, -1], [4, 3, -1]],
+ source=0,
+ destination=1,
+ target=5,
+ )
+ )
+ print(
+ obj.modifiedGraphEdges(
+ n=3, edges=[[0, 1, -1], [0, 2, 5]], source=0, destination=2, target=6
+ )
+ )
+ print(
+ obj.modifiedGraphEdges(
+ n=4,
+ edges=[[1, 0, 4], [1, 2, 3], [2, 3, 5], [0, 3, -1]],
+ source=0,
+ destination=2,
+ target=6,
+ )
+ )