What is the primary technique to solve the Modify Graph Edge Weights problem?

The problem primarily involves graph traversal using algorithms like Dijkstra's combined with heap (priority queue) techniques to modify edge weights.

How do you ensure the shortest path matches the target?

By carefully adjusting the weights of edges with -1 and using a priority queue to maintain the shortest path, ensuring the target is met.

What happens if it's impossible to achieve the target distance?

If no valid modifications can achieve the target distance, the solution should return an empty array.

How do you handle multiple edges with weight -1?

Multiple edges with weight -1 should be handled by modifying them in a way that maintains the shortest path to the target, ensuring no conflicts arise.

What are the common mistakes in solving this problem?

Common mistakes include failing to check if achieving the target is possible, incorrectly modifying edge weights, and overlooking edge cases like unreachable targets.

#2699

Hard

auto_awesome堆

LeetCode 题解工作台

修改图中的边权

给你一个 n 个节点的无向带权连通图，节点编号为 0 到 n - 1 ，再给你一个整数数组 edges ，其中 edges[i] = [a i , b i , w i ] 表示节点 a i 和 b i 之间有一条边权为 w i 的边。部分边的边权为 -1 （ w i = -1 ），其他边的边权…

图堆（优先队列）最短路径

题目描述

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

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

你需要将所有边权为 -1 的边都修改为范围 [1, 2 * 10⁹] 中的 正整数 ，使得从节点 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 <= a_i, b_i< n
w_i = -1 或者 1 <= w_i<= 10⁷
a_i!= b_i
0 <= source, destination < n
source != destination
1 <= target <= 10⁹
输入的图是连通图，且没有自环和重边。

lightbulb

解题思路

方法一：最短路（Dijkstra 算法）

我们先不考虑边权为 $-1$ 的边，使用 Dijkstra 算法求出从 $source$ 到 $destination$ 的最短距离 $d$ 。

如果 $d \lt target$ ，说明存在一条完全由正权边组成的最短路径，此时无论我们如何修改边权为 $-1$ 的边，都无法使得 $source$ 到 $destination$ 的最短距离等于 $target$ ，因此不存在满足题意的修改方案，返回一个空数组即可。

如果 $d = target$ ，说明存在一条完全由正权边组成的、长度为 $target$ 的最短路径，此时我们可以将所有边权为 $-1$ 的边修改为最大值 $2 \times 10^9$ 即可。

如果 $d \gt target$ ，我们可以尝试往图中加入一条边权为 $-1$ 的边，将边权设置为 $1$ ，然后再次使用 Dijkstra 算法求出从 $source$ 到 $destination$ 的最短距离 $d$ 。

如果最短距离 $d \leq target$ ，说明加入这条边后，可以使得最短路变短，而且最短路也一定经过这条边，那么我们只需要将这条边的边权改为 $target-d+1$ ，就可以使得最短路等于 $target$ 。然后我们将其余的边权为 $-1$ 的边修改为最大值 $2 \times 10^9$ 即可。
如果最短距离 $d \gt target$ ，说明加入这条边后，最短路不会变短，那么我们贪心地将这条边的边权保持为 $-1$ ，然后继续尝试加入其余的边权为 $-1$ 的边。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是图中的点数。

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

class Solution:
    def modifiedGraphEdges(
        self, n: int, edges: List[List[int]], source: int, destination: int, target: int
    ) -> List[List[int]]:
        def dijkstra(edges: List[List[int]]) -> int:
            g = [[inf] * n for _ in range(n)]
            for a, b, w in edges:
                if w == -1:
                    continue
                g[a][b] = g[b][a] = w
            dist = [inf] * n
            dist[source] = 0
            vis = [False] * n
            for _ in range(n):
                k = -1
                for j in range(n):
                    if not vis[j] and (k == -1 or dist[k] > dist[j]):
                        k = j
                vis[k] = True
                for j in range(n):
                    dist[j] = min(dist[j], dist[k] + g[k][j])
            return dist[destination]

        inf = 2 * 10**9
        d = dijkstra(edges)
        if d < target:
            return []
        ok = d == target
        for e in edges:
            if e[2] > 0:
                continue
            if ok:
                e[2] = inf
                continue
            e[2] = 1
            d = dijkstra(edges)
            if d <= target:
                ok = True
                e[2] += target - d
        return edges if ok else []

speed

复杂度分析

指标	值
时间	O(E \times (V + E) \log V)
空间	O(V + E)

psychology

面试官常问的追问

外企场景

question_mark
Ensure the candidate applies graph traversal techniques like Dijkstra's or Bellman-Ford to efficiently solve the problem.
question_mark
Look for the candidate's ability to implement priority queues and modify edge weights dynamically.
question_mark
Evaluate how the candidate handles edge cases where the target distance is not achievable.

warning

常见陷阱

外企场景

error
Not checking the feasibility of achieving the target distance before attempting to modify edge weights.
error
Incorrectly assigning edge weights without considering their impact on the shortest path.
error
Overlooking edge cases where no valid solution exists and returning an empty array.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend the problem to allow negative weights and test how the algorithm handles this scenario.
arrow_right_alt
Consider modifying the graph with additional constraints, such as limiting the total number of edge modifications.
arrow_right_alt
Optimize the algorithm for larger graphs, improving efficiency with advanced graph traversal methods or heuristics.

help

常见问题

外企场景

继续练习

#2662 前往目标的最小代价 #2642 设计可以求最短路径的图类 #2577 在网格图中访问一个格子的最少时间