修改图中的边权

标签: 图 最短路 堆（优先队列）

难度: Hard

给你一个 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
  • 输入的图是连通图，且没有自环和重边。

Submission

运行时间: 307 ms

内存: 19.0 MB

from typing import List


class Solution:
    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[
        List[int]]:
        g = [[] for _ in range(n)]
        for i, edge in enumerate(edges):
            g[edge[0]].append((edge[1], i))
            g[edge[1]].append((edge[0], i))

        dis = [[float('inf'), float('inf')] for _ in range(n)]

        dis[source] = [0, 0]

        def dijkstra(k):
            visited = [False] * n
            while True:
                min_dis = float('inf')
                min_index = -1
                for i in range(n):
                    if not visited[i] and (min_index < 0 or dis[i][k] < min_dis):
                        min_dis = dis[i][k]
                        min_index = i
                if min_index == destination or min_index < 0:
                    return
                visited[min_index] = True
                for nid, eid in g[min_index]:
                    wt = edges[eid][2]
                    if wt < 0:
                        wt = 1
                    if k == 1 and edges[eid][2] == -1:
                        w = target - dis[min_index][1] - (dis[destination][0] - dis[nid][0])
                        if w > wt:
                            edges[eid][2] = wt = w
                    dis[nid][k] = min(dis[nid][k], dis[min_index][k] + wt)

        dijkstra(0)
        if dis[destination][0] > target:
            return []
        dijkstra(1)
        if dis[destination][1] < target:
            return []

        for e in edges:
            if e[2] == -1:  # 剩余没修改的边全部改成 1
                e[2] = 1
        return edges


if __name__ == '__main__':
    r = Solution().modifiedGraphEdges(5, [[4, 1, -1], [2, 0, -1], [0, 3, -1], [4, 3, -1]], 0, 1, 5)
    print(r)

Explain

这个题解利用了改良版的Dijkstra算法来找到图中两次的最短路径。首先，构建一个邻接表g来存储图的结构。对于具有边权为-1的边，初始化它们为1（暂定的最小正整数）。接着，使用dijkstra函数来更新节点到源点的最短路径距离。dijkstra被调用两次：第一次确定无修改的最短路径，第二次在此基础上尝试通过调整-1边权，使目标节点到源点的最短路径正好等于target。如果第一次Dijkstra后发现已经超过target，则直接返回空数组。如果第二次调整后的最短路径小于target，同样返回空数组。只有当第二次调整后的最短路径等于target时，将所有未修改的边权设为1后返回结果。

时间复杂度: O(V^2)

空间复杂度: O(V+E)

from typing import List


class Solution:
    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
        g = [[] for _ in range(n)]  # 创建邻接表
        for i, edge in enumerate(edges):
            g[edge[0]].append((edge[1], i))  # 加入无向边
            g[edge[1]].append((edge[0], i))

        dis = [[float('inf'), float('inf')] for _ in range(n)]  # 初始化距离数组

        dis[source] = [0, 0]  # 源点到自己的距离为0

        def dijkstra(k):  # Dijkstra算法实现
            visited = [False] * n  # 访问状态数组
            while True:
                min_dis = float('inf')
                min_index = -1
                for i in range(n):  # 找到未访问的最小距离节点
                    if not visited[i] and (min_index < 0 or dis[i][k] < min_dis):
                        min_dis = dis[i][k]
                        min_index = i
                if min_index == destination or min_index < 0:
                    return
                visited[min_index] = True
                for nid, eid in g[min_index]:
                    wt = edges[eid][2]
                    if wt < 0:
                        wt = 1  # 默认-1权重边为1
                    if k == 1 and edges[eid][2] == -1:
                        w = target - dis[min_index][1] - (dis[destination][0] - dis[nid][0])  # 调整边权以符合目标距离
                        if w > wt:
                            edges[eid][2] = wt = w
                    dis[nid][k] = min(dis[nid][k], dis[min_index][k] + wt)

        dijkstra(0)
        if dis[destination][0] > target:
            return []  # 超过目标距离，返回空数组
        dijkstra(1)
        if dis[destination][1] < target:
            return []  # 调整后距离仍然小于目标，返回空数组

        for e in edges:
            if e[2] == -1:  # 修改剩余未确定的边权
                e[2] = 1
        return edges  # 返回修改后的边集

if __name__ == '__main__':
    r = Solution().modifiedGraphEdges(5, [[4, 1, -1], [2, 0, -1], [0, 3, -1], [4, 3, -1]], 0, 1, 5)
    print(r)

Explore

在这个题解中，将边权为-1的边初始化为1是为了保证在第一次运行Dijkstra算法时，所有边都具有有效的正权重，这样才能正确地计算出从源点到其他节点的最短路径。选择1作为初始化权重是因为1是最小的正整数，这样可以最小化对最短路径的影响，使得后续调整这些边的权重时有更大的灵活性。如果初始化为更大的数值，可能会导致第一次计算得到的路径过长，限制了调整边权以满足目标路径需求的可能性。

在第二次运行Dijkstra算法时，对于边权原本为-1的边，其新权值w的决定是基于以下逻辑：首先计算在不考虑该边的情况下，从源点到当前边的起点已经走过的距离，加上从这条边的终点到目标节点的最短路径（这是从第一次Dijkstra的结果中获得），这两者之和与目标距离target的差值即为这条边应该调整到的新权值。这样的调整确保了通过这条边后，整个路径的总长度恰好等于target。如果这个计算出的权值大于之前的权值（比如初始化的1），则进行更新，否则保持不变。

是的，这个逻辑基于这样一个假设：如果在所有边权为-1的边都被初始化为最小正整数1之后，从源点到目标点的最短路径已经超过了目标距离target，那么即使对这些边权进行调整，也无法使路径长度减小到等于target。因此，如果第一次计算的结果已经超过了target，继续尝试调整边权的操作将是无效的，因为我们只能增加边权，不可能减少已经计算出的最短路径长度。