根据dijkstra的过程,可以求出k到每个点的最短传递时间
而且是依次找最短的,只要返回最大的dist即可
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# dijkstra(单源最短路)
g = [[inf] * n for _ in range(n)]
for u, v, w in times:
g[u - 1][v - 1] = w
dist = [inf] * n
visit = [False] * n
# init
dist[k - 1] = 0
for _ in range(n):
# nextMinDist
x = -1
for y, v in enumerate(visit):
if not v and (x == -1 or dist[y] < dist[x]):
x = y
# update
visit[x] = True
for y, v in enumerate(dist):
if not visit[y]:
dist[y] = min(dist[y], dist[x] + g[x][y])
ans = max(dist)
return ans if ans < inf else -1
dijkstra模板