743.网络延迟时间

链接：743.网络延迟时间
难度：Medium
标签：深度优先搜索、广度优先搜索、图、最短路、堆（优先队列）
简介：现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

题解 1 - typescript

• 编辑时间：2021-08-02
• 执行用时：108ms
• 内存消耗：45.8MB
• 编程语言：typescript
• 解法介绍：哈希储存，每次删减。

class NetNode {
  next: [NetNode, number][] = [];
  constructor(public val: number) {}
}
function getMap(times: number[][]): Map<number, NetNode> {
  const map = new Map<number, NetNode>();
  for (const [start, end, time] of times) {
    let startNode = map.get(start);
    if (!startNode) map.set(start, (startNode = new NetNode(start)));
    let endNode = map.get(end);
    if (!endNode) map.set(end, (endNode = new NetNode(end)));
    startNode.next.push([endNode, time]);
  }
  return map;
}
function networkDelayTime(times: number[][], n: number, k: number): number {
  const map = getMap(times);
  const init = map.get(k)!;
  const q: [NetNode, number][] = [[init, 0]];
  const set = new Set<NetNode>();
  let ans = -1;
  while (q.length) {
    const nextQ: [NetNode, number][] = [];
    let f = false;
    while (q.length) {
      const info = q.shift()!;
      if (set.has(info[0])) continue;
      f = true;
      if (info[1] === 0) {
        set.add(info[0]);
        for (const [next, time] of info[0].next) {
          if (time !== 0) set.has(next) || nextQ.push([next, time - 1]);
          else q.push([next, time]);
        }
      } else {
        info[1]--;
        nextQ.push(info);
      }
    }
    q.push(...nextQ);
    if (f) ans++;
  }
  return set.size === n ? ans : -1;
}

题解 2 - python

• 编辑时间：2024-11-25
• 执行用时：6ms
• 内存消耗：18.07MB
• 编程语言：python
• 解法介绍：bfs。

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        nodes = [[] for _ in range(n + 1)]
        for t in times: nodes[t[0]].append(t)
        q = [(0, k)]
        used = { k: 0 }
        used2 = set([k])
        while q:
            t, node = heappop(q)
            used2.add(node)
            if len(used2) == n: return t
            for time in nodes[node]:
                _, child, time_offset = time
                next_time = time_offset + t
                if child not in used or next_time < used[child]:
                    used[child] = next_time
                    heappush(q, (next_time, child))
        return -1