leetcode：743. 网络延迟时间【单源最短路 + dijkstra模板】

分析

根据dijkstra的过程，可以求出k到每个点的最短传递时间
而且是依次找最短的，只要返回最大的dist即可

ac code

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

总结

dijkstra模板