Problem

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] = [aᵢ, bᵢ, wᵢ] indicates that there is an edge between nodes aᵢ and bᵢ with weight wᵢ.

Some edges have a weight of -1 (wᵢ = -1), while others have a positive weight (wᵢ > 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⁹] 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.

https://leetcode.com/problems/modify-graph-edge-weights/

Example 1:

case1

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:

case2

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:

case3

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 <= aᵢ, bᵢ < n
  • wᵢ = -1 or 1 <= wᵢ <= 10⁷
  • aᵢ != bᵢ
  • 0 <= source, destination < n
  • source != destination
  • 1 <= target <= 10⁹
  • The graph is connected, and there are no self-loops or repeated edges

Test Cases

1
2
class Solution:
    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
solution_test.py
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
from collections import defaultdict
from heapq import heappop, heappush
from math import inf
import pytest

from solution import Solution


@pytest.mark.parametrize('n, edges, source, destination, target, expected', [
    (
        5, [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], 0, 1, 5,
        [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
    ),
    (
        3, [[0,1,-1],[0,2,5]], 0, 2, 6,
        []
    ),
    (
        4, [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], 0, 2, 6,
        [[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
    ),

    (
        4, [[0,1,5],[1,2,7],[2,3,7],[3,1,9],[3,0,-1],[0,2,-1]], 2, 3, 7,
        [[0,1,5],[1,2,7],[2,3,7],[3,1,9],[3,0,1000000005],[0,2,6]]
    ),
    (
        4, [[0,1,1],[1,2,2],[2,3,3]], 0, 2, 1,
        []
    ),

    (
        4, [[0,1,-1], [1,2,-1], [2,3,1], [1,3,5]], 3, 0, 10,
        [[0,1,1], [1,2,8], [2,3,1], [1,3,5]]
    ),
    (
        4, [[0,1,-1], [1,2,-1], [2,3,1], [1,3,5]], 0, 3, 10,
        [[0,1,8], [1,2,1], [2,3,1], [1,3,5]]
    ),
])
class Test:
    def test_solution(self, n, edges, source, destination, target, expected):
        sol = Solution()
        res = sol.modifiedGraphEdges(n, edges.copy(), source, destination, target)
        res = self._sort(res)
        expected = self._sort(expected)
        if res != expected:
            edges = self._sort(edges)
            self._verify(n, edges, source, destination, target, res)

    def _sort(self, edges):
        return sorted((*sorted(e[:2]), e[2]) for e in edges)

    def _verify(self, n, origin, source, destination, target, result):
        assert len(result) == len(origin)
        for r, o in zip(result, origin):
            if o[2] == -1:
                assert r[:2] == o[:2]
                assert r[2] > 0
            else:
                assert r == o

        graph = defaultdict(dict)
        for u, v, w in result:
            graph[u][v] = graph[v][u] = w if w > 0 else inf

        # Dijkstra.
        dists = [inf] * n # dist[u]: the distance from source to u.
        dists[source] = 0
        queue = [(0, source)] # A min-heap queue of (dists[u], u)
        while queue:
            dist, u = heappop(queue)
            if u == destination:
                assert dist == target
                return
            elif dist > dists[u]: # Duplicated vertex in queue.
                continue

            # Update u's not-done adjacent vertices' distances.
            for v, w in graph[u].items():
                if dist + w < dists[v]:
                    dists[v] = dist + w
                    heappush(queue, (dists[v], v))

        assert False # `destination` is not reachable from`source`.

Thoughts

先要实现一番测试代码，因为结果的不确定性，需要单独验证结果是否正确。在测试代码中用 Dijkstra 算法对 Solution.modifiedGraphEdges 返回的边的信息，计算 source 到 destination 的最短距离，看是不是刚好等于 target。

首先假设那些权重为 -1 的边（简称「-1 边」）都不存在，调用 Dijkstra 算法计算 source 到 destination 的最短距离，记为 dist（不通则为 ∞）。显然如果 dist < target，那就无解（类似于 Example 2），直接返回空数组。如果 dist = target 那就不需要做任何有意义的修改（当然题目要求所有 -1 边都必须改成 [1, 2 * 10⁹] 内的正数，那就全都改成 2 * 10⁹ 即可）。如果 dist > target 但是 edges 中没有 -1 边，也无解，直接返回空数组。

Dijkstra 算法的更多信息在 2290. Minimum Obstacle Removal to Reach Corner 有提到。

然后把所有 -1 边的权重都临时改为 1，再调用 Dijkstra 算法计算 source 到 destination 的最短距离，同样记为 dist。如果 dist > target 说明怎么改都无法把最短距离缩减到 target，直接返回空数组。如果 dist = target，那么把最短路径上所有 -1 边的权重都改为 1（同时按题目要求把其他 -1 边的权重改成 2 * 10⁹）即可。

如果 dist < target 就会麻烦一些。一个想法是令 gap = target - dist，在最短路径上任选一条 -1 边，将其权重改为 1 + gap（其他的都改为 1）。但这样改完之后，source 到 destination 的最短路径可能会变化，导致最短距离变得小于 target，比如下面这个情况（source = 0, destination = 3, target = 10）：

把所有 -1 边的权重改成 1 之后，找到最短路径 0 - 1 - 2 - 3（蓝色），距离为 dist = 3。如果把 target - dist = 7 随机地加到了边 (1, 2) 上，就会导致最短路径变成 0 - 1 - 3（红色），距离为 6，小于 target 了。

可以按最新的权重重新计算 source 到 destination 的最短距离，如果得到了比 target 小的最短距离，就再任选一条 -1 边，把新的到 gap 加上去。比如上图中，新的 gap 值为 4，任选一条红色路径上的 -1 边（如 (0, 1)），把 4 加上去，得到下图的结果：

重复这一操作直到最短距离等于 target。

所以至少需要做两次 Dijkstra 最短路径计算，时间是 O((E + n) log n)（其中 E 是 edges 的长度）。但是在调整 -1 边权重的时候，最坏情况可能会需要重新计算 O(n) 次最短路径，总的时间复杂度为 O(n (E + n) log n)，约等于 O(n³ log n)（因为 O(E) ≈ O(n²)）。空间复杂度 O(E)。

提交之后运行时间还可以，97+%。

还有一个调整权重的方法，对于一条在最短路径上的 -1 边 (u, v)，取 source 到 u 的最短距离 dist1，和 v 到 destination 的最短距离 dist2，那么把 (u, v) 的权重改成 target - dist1 - dist2。但是这个操作不能连续执行，修改完一条 -1 边的权重之后，对于另外一条 -1 边 (u', v')，需要重新计算 dist1' 和 dist2'，复杂度是差不多的。

Code

solution.py
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from collections import defaultdict
from heapq import heappop, heappush
from math import inf


class Solution:
    def modifiedGraphEdges(self, n: int, edges: list[list[int]], source: int, destination: int, target: int) -> list[list[int]]:
        MAX = 2_000_000_000
        graph = defaultdict(dict)
        modifies = set()
        for u, v, w in edges:
            graph[u][v] = graph[v][u] = w
            if w < 0: modifies.add((u, v) if u < v else (v, u))

        def dijkstra(re_weight: int) -> tuple[list[int], list[int]]:
            dists = [inf] * n # dist[u]: the distance from `source` to u.
            predecessors = [None] * n # predecessors[u]: u's previous vertex in the shortest path.
            dists[source] = 0
            queue = [(0, source)] # A min-heap queue of (dists[u], u)
            while queue:
                dist, u = heappop(queue)
                if u == destination:
                    break
                elif dist > dists[u]: # Duplicated vertex in queue.
                    continue

                # Update u's not-done adjacent vertices' distances.
                for v, w in graph[u].items():
                    if w < 0: w = re_weight
                    if dist + w < dists[v]:
                        dists[v] = dist + w
                        predecessors[v] = u
                        heappush(queue, (dists[v], v))

            return dists, predecessors

        dist = dijkstra(inf)[0][destination]
        if dist < target:
            return []
        elif dist == target:
            return [[u, v, MAX if w < 0 else w] for u, v, w in edges]
        elif not modifies:
            return []

        while modifies:
            dists, predecessors = dijkstra(1)
            if (gap := target - dists[destination]) < 0:
                return []
            elif gap == 0:
                break

            in_path = set() # intersection(modifies, the shortest path)
            v = destination
            u = predecessors[v]
            while u is not None:
                if graph[u][v] < 0:
                    in_path.add((u, v) if u < v else (v, u))
                u, v = predecessors[u], u

            for u, v in modifies - in_path:
                graph[u][v] = graph[v][u] = MAX

            modifies = in_path
            u, v = modifies.pop()
            graph[u][v] = graph[v][u] = 1 + gap

        return [[u, v, abs(graph[u][v])] for u, v, _ in edges]
hard difficult
参考资料
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~