JZX轻语：简
LeetCode 743 - 网络延迟时间
发表于2024年04月28日
本质就是求单源最短路径，然后返回节点K到其他节点的路径中的最大者即可。
普通的Dijkstra算法：
from collections import deque
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
adj_list = [[] for _ in range(n + 1)]
for u, v, w in times:
adj_list[u].append((v, w))
ans = 0
dis = [-1] * (n + 1)
dis[k] = 0
visited = [False] * (n + 1)
while True:
min_u = -1
min_dis = -1
for u in range(1, n + 1):
if not visited[u] and dis[u] != -1 and (min_dis == -1 or dis[u] < min_dis):
min_u = u
min_dis = dis[u]
if min_u == -1:
break
visited[min_u] = True
ans = max(ans, min_dis)
# relax
for v, w in adj_list[min_u]:
if dis[v] == -1 or dis[v] > dis[min_u] + w:
dis[v] = dis[min_u] + w
if not all(visited[u] for u in range(1, n + 1)):
return -1
return ans使用堆优化的Dijkstra算法,，但实际表现不如上一个：
import heapq
from collections import deque
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
adj_list = [[] for _ in range(n + 1)]
for u, v, w in times:
adj_list[u].append((v, w))
ans = 0
dis = [-1] * (n + 1)
dis[k] = 0
visited = [False] * (n + 1)
pq = []
pq.append((0, k))
while pq:
min_dis, min_u = heapq.heappop(pq)
if visited[min_u]:
continue
visited[min_u] = True
ans = max(ans, min_dis)
# relax
for v, w in adj_list[min_u]:
if dis[v] == -1 or dis[v] > dis[min_u] + w:
dis[v] = dis[min_u] + w
heapq.heappush(pq, (dis[v], v))
if not all(visited[u] for u in range(1, n + 1)):
return -1
return ans