跳到主要内容

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

链接：3112.访问消失节点的最少时间
难度：Medium
标签：图、数组、最短路、堆（优先队列）
简介：请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，那么 answer[i] 为 -1 。

题解 1 - python​

  • 编辑时间：2024-07-18
  • 执行用时：921ms
  • 内存消耗：72.21MB
  • 编程语言：python
  • 解法介绍：图短路求出当前点到其他点的最短时间。
class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        nodes = [defaultdict(lambda :inf) for _ in range(n)]
        for n1, n2, v in edges:
            if n1 != n2:
                nodes[n1][n2] = nodes[n2][n1] = min(nodes[n1][n2], v)
        q = [(0, 0)]
        res = [-1] * n
        res[0] = 0
        used = [False] * n
        while q:
            t, node = heappop(q)
            if used[node]: continue
            used[node] = True
            res[node] = t
            for child in nodes[node].keys():
                next_t = t + nodes[node][child]
                if not used[child] and next_t < disappear[child]:
                    heappush(q, (next_t, child))
        return res