发表于 2024.07.18

• 单源最短路径问题的变种，可使用Dijkstra算法解决。如果从节点0到某个节点i的最短路径大于等于disappear[i]，则该节点不可达，此外，该节点也不可参与松弛操作。因此，只需要在Dijkstra算法中加入这个判断条件即可。

  一开始基于优先队列的算法实现，注意这里的消失条件判断放在了松弛操作之前。

  import heapq
  
  
  class Solution:
      def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
          adj_list = [[] for _ in range(n)]  # type: List[List[tuple[int, int]]]
          for u, v, w in edges:
              adj_list[u].append((v, w))
              adj_list[v].append((u, w))
          dist = [-1] * n
          pq = [(0, 0)]
          while pq:
              d, u = heapq.heappop(pq)
              if dist[u] != -1 or d >= disappear[u]:
                  continue
              dist[u] = d
              # relax
              for v, w in adj_list[u]:
                  heapq.heappush(pq, (d + w, v))
          return dist

  优化：把消失条件判断放在松弛操作之内，这样可以减少一些不必要的堆操作(堆的整理需要O(logN)的时间复杂度)。

  import heapq
  
  
  class Solution:
      def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
          adj_list = [[] for _ in range(n)]  # type: List[List[tuple[int, int]]]
          for u, v, w in edges:
              adj_list[u].append((v, w))
              adj_list[v].append((u, w))
          dist = [-1] * n
          pq = [(0, 0)]
          while pq:
              d, u = heapq.heappop(pq)
              if dist[u] != -1:
                  continue
              dist[u] = d
              # relax
              for v, w in adj_list[u]:
                  if d + w < disappear[v]:
                      heapq.heappush(pq, (d + w, v))
          return dist

• LC 题目链接