#2699
Modify Graph Edge Weights
candidate master · 1300 · lc hard +32 · failed · 55.6% accepted · 738 likes · top 49%
Description
An undirected weighted connected graph has n nodes and edges[i] = [ai, bi, wi]. Edges with wi = -1 may be assigned any positive integer in [1, 2e9]; edges with positive weight are fixed. Assign the -1-weight edges so that the shortest path from source to destination equals target. Return all edges (modified or not), or an empty array if it is impossible.
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.
Code
1
2
3