ダイクストラ法で合図が全部の中継所に届くまでの時間を求める

from heapq import heappop
from heapq import heappush


def network_delay(
    links, n, src
):
    # 中継所ごとの出ている回線
    adj = [[]]
    for _ in range(n):
        adj.append([])
    for a, b, t in links:
        adj[a].append((b, t))
    done = {}
    h = [(0, src)]
    while h:
        d, v = heappop(h)
        if v in done:
            continue
        done[v] = d
        for u, t in adj[v]:
            nd = d + t
            heappush(h, (nd, u))
    if len(done) < n:
        return -1
    return max(done.values())

function networkDelay(
  links, n, src,
) {
  // 中継所ごとの出ている回線
  const adj = [];
  for (let v = 0; v <= n; v++) {
    adj.push([]);
  }
  links.forEach(([a, b, t]) => {
    adj[a].push([b, t]);
  });
  const done = new Map();
  const h = [[0, src]];
  while (h.length) {
    const [d, v] = pop(h);
    if (done.has(v)) {
      continue;
    }
    done.set(v, d);
    for (const e of adj[v]) {
      const [u, t] = e;
      push(h, [d + t, u]);
    }
  }
  if (done.size < n) {
    return -1;
  }
  const ds = [...done.values()];
  return Math.max(...ds);
}

// [時刻, 中継所] の小さい順のヒープ
function push(h, x) {
  h.push(x);
  let i = h.length - 1;
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (h[p][0] <= h[i][0]) {
      return;
    }
    [h[p], h[i]] = [h[i], h[p]];
    i = p;
  }
}

function pop(h) {
  const top = h[0];
  const last = h.pop();
  if (h.length === 0) {
    return top;
  }
  h[0] = last;
  const n = h.length;
  let i = 0;
  while (true) {
    let s = i;
    const l = 2 * i + 1;
    const r = l + 1;
    if (l < n &&
      h[l][0] < h[s][0]) {
      s = l;
    }
    if (r < n &&
      h[r][0] < h[s][0]) {
      s = r;
    }
    if (s === i) {
      return top;
    }
    [h[s], h[i]] = [h[i], h[s]];
    i = s;
  }
}

import "container/heap"

// {時刻, 中継所} の小さい順のヒープ
type pq [][2]int

func (h pq) Len() int {
	return len(h)
}

func (h pq) Less(
	i, j int,
) bool {
	return h[i][0] < h[j][0]
}

func (h pq) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *pq) Push(x any) {
	*h = append(*h, x.([2]int))
}

func (h *pq) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func networkDelay(
	links [][]int, n, src int,
) int {
	adj := map[int][][2]int{}
	for _, e := range links {
		a := e[0]
		adj[a] = append(adj[a],
			[2]int{e[1], e[2]})
	}
	done := map[int]int{}
	h := &pq{{0, src}}
	for h.Len() > 0 {
		top := heap.Pop(h).([2]int)
		d, v := top[0], top[1]
		if _, ok := done[v]; ok {
			continue
		}
		done[v] = d
		for _, e := range adj[v] {
			heap.Push(h,
				[2]int{d + e[1], e[0]})
		}
	}
	if len(done) < n {
		return -1
	}
	best := 0
	for _, d := range done {
		best = max(best, d)
	}
	return best
}