LeetCode 筆記 - 743. Network Delay Time

Posted on

題目在此 743. Network Delay Time

給定一個 Graph 與每個邊的方向與權重，指定一個 node 計算出訊號抵達所有 node 的時間

解題思維

這題就是要你各位實作 Dijkstra’s algorithm
完成✅image 106

程式碼

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
27
28
29
30
31

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:

        graph = collections.defaultdict(list)

        for i in range(len(times)):
            u, v, time = times[i]
            graph[u].append((v, time))

        results = [inf] * (n + 1)
        results[k] = 0

        queue = [(k, 0)]
        while queue:
            cur_node, cur_time = heapq.heappop(queue)

            for next_node, next_time in graph[cur_node]:

                next_time += cur_time

                if next_time < results[next_node]:
                    results[next_node] = next_time
                    heapq.heappush(queue, (next_node, next_time))

        # results[0] is not used
        results = results[1:]
        
        if inf in results:
            return -1
        return max(results)
image 106

也許你也會想看看