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;
}

题解 1 - typescript​

题解 1 - typescript