LeetCode 筆記 - 743. Network Delay Time

Posted on Edited on

題目在此 743. Network Delay Time

看到這題的時候，感覺好像在考閱讀測驗
給定一個 Graph 與每個邊的方向與權重，指定一個 node 計算出訊號抵達所有 node 的時間

解題思維

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

程式碼

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:

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

        length = n + 1
        table = [[-1, None, False] for _ in range(length)]
        table[k][0] = 0

        time_map = {}
        for t in times:
            source, target, time = t[0], t[1], t[2]
            if source not in time_map:
                time_map[source] = []
            time_map[source].append((target, time))

        while True:
            # pick the shortest node
            min_dis = None
            min_node = None
            for i in range(length):
                t = table[i]
                if t[0] == -1:
                    continue
                if t[2]:
                    continue
                if min_dis is None or t[0] < min_dis:
                    min_dis = t[0]
                    min_node = i
            if min_node is None:
                break
            table[min_node][2] = True

            if min_node not in time_map:
                continue
            for target, time in time_map[min_node]:
                if table[target][2]:
                    continue
                if table[target][0] == -1 or table[min_node][0] + time < table[target][0]:
                    table[target][0] = table[min_node][0] + time
                    table[target][1] = min_node

        result = None
        for t in table[1:]:
            if t[0] == -1:
                return -1
            if result is None or result < t[0]:
                result = t[0]
        return result