diff options
author | Jack Sangdahl <[email protected]> | 2024-08-29 19:50:30 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-29 19:50:30 -0600 |
commit | accfdfe3a52d62bee9b2c24dece6f2b613ceeb7c (patch) | |
tree | ceaf6bad9cb34fb6f6a6ca3080df3496751bf723 | |
parent | 7dc61c9997c53be6c50726f2a618df397f9ac09f (diff) | |
download | leetcode-accfdfe3a52d62bee9b2c24dece6f2b613ceeb7c.tar.gz leetcode-accfdfe3a52d62bee9b2c24dece6f2b613ceeb7c.zip |
2699. modify graph edge weights
-rw-r--r-- | modify_graph_edge_weight.cpp | 91 | ||||
-rw-r--r-- | modify_graph_edge_weight.py | 106 |
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, + ) + ) |