743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

提示：

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• 所有 (ui, vi) 对都 互不相同（即，不含重复边）

DFS BFS 中等

我写的这个有点像 Dijkstra 算法，就是 BFS 统计时间

代码

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = defaultdict(list)
        for t in times:
            g[t[0]].append((t[1],t[2]))
        q = deque([(k, 0)])
        visited = {k:0}
        while q:
            q_len = len(q)
            for _ in range(q_len):
                cur, t = q.popleft()
                for nei, w in g[cur]:
                    if (nei in visited and w+t < visited[nei]) or nei not in visited:
                        q.append((nei, w+t))
                        visited[nei] = w+t
        if len(visited) != n:
            return -1
        time = -1
        for k, v in visited.items():
            time = max(time,v)
        return time