Time for a signal to reach every node

import heapq

def network_delay(times, n, k):
    adj = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))
    dist = {}                              # node -> final arrival time
    heap = [(0, k)]
    while heap:
        t, u = heapq.heappop(heap)
        if u in dist:
            continue                       # a stale entry: u was settled earlier
        dist[u] = t
        for v, w in adj[u]:
            if v not in dist:
                heapq.heappush(heap, (t + w, v))
    return max(dist.values()) if len(dist) == n else -1

#include <vector>
#include <queue>
#include <functional>
#include <algorithm>

int solve(const std::vector<std::vector<int>>& times, int n, int k) {
    std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
    for (const auto& e : times) adj[e[0]].push_back({e[1], e[2]});
    std::vector<int> dist(n + 1, -1);              // -1 = not yet settled
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> heap;
    heap.push({0, k});
    while (!heap.empty()) {
        auto [t, u] = heap.top();
        heap.pop();
        if (dist[u] != -1) continue;               // a stale entry
        dist[u] = t;
        for (auto [v, w] : adj[u]) if (dist[v] == -1) heap.push({t + w, v});
    }
    int worst = 0;
    for (int v = 1; v <= n; ++v) {
        if (dist[v] == -1) return -1;
        worst = std::max(worst, dist[v]);
    }
    return worst;
}

import java.util.*;

class Solution {
    public int networkDelay(int[][] times, int n, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int[] e : times) adj.get(e[0]).add(new int[]{e[1], e[2]});
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);                          // -1 = not yet settled
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.add(new int[]{0, k});
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int t = top[0], u = top[1];
            if (dist[u] != -1) continue;                // a stale entry
            dist[u] = t;
            for (int[] e : adj.get(u)) if (dist[e[0]] == -1) heap.add(new int[]{t + e[1], e[0]});
        }
        int worst = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == -1) return -1;
            worst = Math.max(worst, dist[v]);
        }
        return worst;
    }
}

function networkDelay(times, n, k) {
  const adj = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u].push([v, w]);
  // a binary heap of [time, node]
  const heap = [];
  const push = e => { heap.push(e); let i = heap.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (heap[p][0] <= heap[i][0]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
  const pop = () => { const top = heap[0], last = heap.pop(); if (heap.length) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < heap.length && heap[l][0] < heap[m][0]) m = l; if (r < heap.length && heap[r][0] < heap[m][0]) m = r; if (m === i) break; [heap[m], heap[i]] = [heap[i], heap[m]]; i = m; } } return top; };
  const dist = new Map();                  // node -> final arrival time
  push([0, k]);
  while (heap.length) {
    const [t, u] = pop();
    if (dist.has(u)) continue;             // a stale entry
    dist.set(u, t);
    for (const [v, w] of adj[u]) if (!dist.has(v)) push([t + w, v]);
  }
  return dist.size === n ? Math.max(...dist.values()) : -1;
}

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn solve(times: &[[i64; 3]], n: i64, k: i64) -> i64 {
    let n = n as usize;
    let mut adj: Vec<Vec<(usize, i64)>> = vec![Vec::new(); n + 1];
    for e in times {
        adj[e[0] as usize].push((e[1] as usize, e[2]));
    }
    let mut dist: Vec<Option<i64>> = vec![None; n + 1];
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i64, k as usize)));
    while let Some(Reverse((t, u))) = heap.pop() {
        if dist[u].is_some() {
            continue;                                  // a stale entry
        }
        dist[u] = Some(t);
        for &(v, w) in &adj[u] {
            if dist[v].is_none() {
                heap.push(Reverse((t + w, v)));
            }
        }
    }
    let mut worst = 0;
    for v in 1..=n {
        match dist[v] {
            None => return -1,
            Some(d) => worst = worst.max(d),
        }
    }
    worst
}

import qualified Data.Map.Strict as M
import qualified Data.Set as S

solve :: [[Int]] -> Int -> Int -> Int
solve times n k = go (S.singleton (0, k)) M.empty
  where
    adj = M.fromListWith (++) [(u, [(v, w)]) | [u, v, w] <- times]
    -- the set is the heap: its minimum is the smallest (time, node) entry
    go heap dist = case S.minView heap of
      Nothing -> if M.size dist == n then maximum (M.elems dist) else -1
      Just ((t, u), rest)
        | M.member u dist -> go rest dist                  -- a stale entry
        | otherwise ->
            let dist' = M.insert u t dist
                next  = [(t + w, v) | (v, w) <- M.findWithDefault [] u adj, not (M.member v dist')]
            in go (foldr S.insert rest next) dist'