3112. 访问消失节点的最少时间

题目描述

给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。

同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。

注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。

请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，那么 answer[i] 为 -1 。

思路

考虑到边的数量最大值可能为 50000，因此可以按照存储稀疏图的方式去存储图并使用 Dijkstra 算法去求最短距离，可以参考 743. 网络延迟时间这道题目的第二种解法。

由于图是无向的，因此在存储图的时候我们要将两边都加进去：

class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        g = [[] for _ in range(n)]
        for x, y, d in edges:
            g[x].append((y, d))
            g[y].append((x, d))

接下来用一个数组 dis 保存最短路，实际上这也是本题的返回值：

        dis = [-1] * n
        dis[0] = 0

用一个堆表示当前最短路。我们先只考虑最短路径，不考虑节点消失的时间：

        h = [(0, 0)]
        while h:
            dx, x = heappop(h)
            if dx > dis[x]:
                continue
            for y, d in g[x]:
                new_dis = dx+d
                if dis[y]<0 or new_dis < dis[y]:
                    dis[y] = new_dis
                    heappush(h, (new_dis, y))

节点消失时间其实就是在更新邻居时判断，最终代码为：

class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        g = [[] for _ in range(n)]
        for x, y, d in edges:
            g[x].append((y, d))
            g[y].append((x, d))
 
        dis = [-1] * n
        dis[0] = 0
 
        h = [(0, 0)]
        while h:
            dx, x = heappop(h)
            if dx > dis[x]:
                continue
            for y, d in g[x]:
                new_dis = dx+d
                if new_dis >= disappear[y]:
                    continue
                if dis[y] < 0 or new_dis < dis[y]:
                    dis[y] = new_dis
                    heappush(h, (new_dis, y))
 
        for i in range(n):
            if dis[i] == inf:
                dis[i] = -1
        return dis

想得太多