2699：修改图中的边权（2873 分）

力扣第 346 场周赛第 4 题

题目

给你一个 n 个节点的 无向带权连通 图，节点编号为 0 到 n - 1 ，再给你一个整数数组 edges ，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。

部分边的边权为 -1（wi = -1），其他边的边权都为 正 数（wi > 0）。

你需要将所有边权为 -1 的边都修改为范围 [1, 2 * 109] 中的 正整数 ，使得从节点 source 到节点 destination 的 最短距离 为整数 target 。如果有 多种 修改方案可以使 source 和 destination 之间的最短距离等于 target ，你可以返回任意一种方案。

如果存在使 source 到 destination 最短距离为 target 的方案，请你按任意顺序返回包含所有边的数组（包括未修改边权的边）。如果不存在这样的方案，请你返回一个 空数组 。

注意：你不能修改一开始边权为正数的边。

示例 1：

输入：n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
输出：[[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
解释：上图展示了一个满足题意的修改方案，从 0 到 1 的最短距离为 5 。

示例 2：

输入：n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
输出：[]
解释：上图是一开始的图。没有办法通过修改边权为 -1 的边，使得 0 到 2 的最短距离等于 6 ，所以返回一个空数组。

示例 3：

输入：n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6
输出：[[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
解释：上图展示了一个满足题意的修改方案，从 0 到 2 的最短距离为 6 。

提示：

• 1 <= n <= 100
• 1 <= edges.length <= n * (n - 1) / 2
• edges[i].length == 3
• 0 <= ai, bi < n
• wi = -1 或者 1 <= wi <= 107
• ai != bi
• 0 <= source, destination < n
• source != destination
• 1 <= target <= 109
• 输入的图是连通图，且没有自环和重边。

分析

• 先给所有-1边赋权1，跑一趟最短路得到 d[v] 代表终点 e 到 v 的最短距离，这也是理论上的最短距离
  • 如果 d[s]>target，显然不存在解
• 假设 s 到 e 的最短路径上第一个-1边是 (u,v)，显然可以增大该边权，使得该路径总和为target
• 但修改后该路径不一定是最短路径了，需要继续修改剩下的最短路径
• 因此再从 s 出发，边跑最短路，边修改-1边，这样修改后不影响之前的最短路径，接着跑最短路即可，可以一趟解决

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
        def push(w,u,d):
            if w<d[u]:
                d[u] = w
                heappush(pq,(w,u))
        
        E = edges
        s,e,t = source,destination,target
        g = [[] for _ in range(n)]
        for i,(u,v,w) in enumerate(E):
            g[u].append((v,i))
            g[v].append((u,i))
        pq = [(0,e)]
        d = [inf]*n
        d[e] = 0
        while pq:
            w,u = heappop(pq)
            if w>d[u]:
                continue
            for v,i in g[u]:
                w2 = max(1,E[i][2])
                push(w+w2,v,d)
        if d[s]>t:
            return []
        pq = [(0,s)]
        f = [inf]*n
        f[s] = 0
        while pq:
            w,u = heappop(pq)
            if w>f[u]:
                continue
            for v,i in g[u]:
                w2 = E[i][2]
                if w2==-1:
                    w2 = max(1,t-f[u]-d[v])
                    E[i][2] = w2
                push(w+w2,v,f)
        return E if f[e]==t else []

283 ms