# Solving Leetcode Interviews in Seconds with AI: Modify Graph Edge Weights # Introduction In this blog post, we will explore how to solve the LeetCode problem "2699" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months. # Problem Statement > 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 others 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 * 109] 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 between source and destination equal to target, any of them will be considered correct. Return an array containing all edges (even unmodified ones) in any order if it is possible to make the shortest distance from source to destination equal to target, or an empty array if it's impossible. Note: You are not allowed to modify the weights of edges with initial positive weights.   Example 1: Input: n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5 Output: [[4,1,1],[2,0,1],[0,3,3],[4,3,1]] Explanation: The graph above shows a possible modification to the edges, making the distance from 0 to 1 equal to 5. Example 2: Input: n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6 Output: [] Explanation: The graph above contains the initial edges. It is not possible to make the distance from 0 to 2 equal to 6 by modifying the edge with weight -1. So, an empty array is returned. Example 3: Input: n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6 Output: [[1,0,4],[1,2,3],[2,3,5],[0,3,1]] Explanation: The graph above shows a modified graph having the shortest distance from 0 to 2 as 6.   Constraints: 1 <= n <= 100 1 <= edges.length <= n * (n - 1) / 2 edges[i].length == 3 0 <= ai, bi < n wi = -1 or 1 <= wi <= 107 ai != bi 0 <= source, destination < n source != destination 1 <= target <= 109 The graph is connected, and there are no self-loops or repeated edges # Explanation Here's the approach, complexity, and Python code for solving this problem: **Approach:** * **Initial Dijkstra (Minimum):** First, run Dijkstra's algorithm treating all `-1` edges as having a weight of `1`. This provides the *minimum possible* shortest path from `source` to `destination`. * **Initial Dijkstra (Maximum):** Next, run Dijkstra's algorithm treating all `-1` edges as having a weight of `2 * 10^9`. This provides the *maximum possible* shortest path from `source` to `destination`. * **Binary Search/Adjustment:** If `target` is outside the range [minimum shortest path, maximum shortest path], it's impossible to achieve the target. Otherwise, iterate through edges. If current shortest path is less than the target, increase the weights of -1 edges and if its larger than target decrease weights of -1 edges, until target is met. **Complexity:** * Runtime: O(E * N * logN), where E is the number of edges and N is the number of nodes. In the worst-case scenario, we perform Dijkstra's Algorithm twice, and then linearly iterate through edges. * Storage: O(N + E) for storing the graph and distances. # Code ```python import heapq def shortest_path(n, adj, source, destination): dist = {i: float('inf') for i in range(n)} dist[source] = 0 pq = [(0, source)] while pq: d, u = heapq.heappop(pq) if d > dist[u]: continue for v, weight in adj[u]: if dist[v] > dist[u] + weight: dist[v] = dist[u] + weight heapq.heappush(pq, (dist[v], v)) return dist[destination] def modify_graph_edges(n, edges, source, destination, target): adj = {i: [] for i in range(n)} negative_edges = [] for i, (u, v, w) in enumerate(edges): adj[u].append((v, w)) adj[v].append((u, w)) if w == -1: negative_edges.append(i) # Minimum possible shortest path (treat -1 as 1) adj_min = {i: [] for i in range(n)} edges_min = [] for u, v, w in edges: adj_min[u].append((v, 1 if w == -1 else w)) adj_min[v].append((u, 1 if w == -1 else w)) edges_min.append((u, v, 1 if w == -1 else w)) min_dist = shortest_path(n, adj_min, source, destination) # Maximum possible shortest path (treat -1 as 2 * 10^9) adj_max = {i: [] for i in range(n)} edges_max = [] max_weight = 2 * 10**9 for u, v, w in edges: adj_max[u].append((v, max_weight if w == -1 else w)) adj_max[v].append((u, max_weight if w == -1 else w)) edges_max.append((u, v, max_weight if w == -1 else w)) max_dist = shortest_path(n, adj_max, source, destination) if not (min_dist <= target <= max_dist): return [] # Create graph with actual edges adj = {i: [] for i in range(n)} for i, (u, v, w) in enumerate(edges): adj[u].append((v, w)) adj[v].append((u, w)) # Adjust negative edge weights to achieve target current_edges = [list(edge) for edge in edges] # Create mutable copy of edges for i in negative_edges: current_edges[i][2] = 1 def calculate_shortest_path(edges_list): current_adj = {i: [] for i in range(n)} for u, v, w in edges_list: current_adj[u].append((v, w)) current_adj[v].append((u, w)) return shortest_path(n, current_adj, source, destination) path = calculate_shortest_path([tuple(edge) for edge in current_edges]) if path < target: diff = target - path for i in reversed(negative_edges): increase = min(diff, 2*10**9-1) current_edges[i][2] += increase diff -= increase if diff ==0: break path_after_increase = calculate_shortest_path([tuple(edge) for edge in current_edges]) if path_after_increase != target: return [] return [list(edge) for edge in current_edges] ```