JZX轻语：简
LeetCode 3112 - 访问消失节点的最少时间
发表于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