61. Network Delay Time

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        adj = defaultdict(list)
        for u, v, w in times:
            adj[u].append((v, w))
        dist = {}
        heap = [(0, k)]
        while heap:                              # Dijkstra
            d, u = heapq.heappop(heap)
            if u in dist:
                continue                         # already finalised with a shorter time
            dist[u] = d
            for v, w in adj[u]:
                if v not in dist:
                    heapq.heappush(heap, (d + w, v))
        return max(dist.values()) if len(dist) == n else -1

class Solution {
    public int networkDelayTime(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[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.add(new int[]{0, k});
        while (!heap.isEmpty()) {                      // Dijkstra
            int[] cur = heap.poll();
            int d = cur[0], u = cur[1];
            if (dist[u] != Integer.MAX_VALUE) continue;
            dist[u] = d;
            for (int[] e : adj.get(u)) if (dist[e[0]] == Integer.MAX_VALUE) heap.add(new int[]{d + e[1], e[0]});
        }
        int best = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            best = Math.max(best, dist[i]);
        }
        return best;
    }
}

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, int>>> adj(n + 1);
        for (auto& t : times) adj[t[0]].push_back({t[1], t[2]});
        vector<int> dist(n + 1, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
        heap.push({0, k});
        while (!heap.empty()) {                        // Dijkstra
            auto [d, u] = heap.top(); heap.pop();
            if (dist[u] != INT_MAX) continue;
            dist[u] = d;
            for (auto [v, w] : adj[u]) if (dist[v] == INT_MAX) heap.push({d + w, v});
        }
        int best = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INT_MAX) return -1;
            best = max(best, dist[i]);
        }
        return best;
    }
};

class MinHeap {
  constructor(less = (a, b) => a < b) { this.a = []; this.less = less; }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) { const a = this.a; a.push(x); let i = a.length - 1;
    while (i > 0) { const p = (i - 1) >> 1; if (!this.less(a[i], a[p])) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } }
  pop() { const a = this.a, top = a[0], last = a.pop();
    if (a.length) { a[0] = last; let i = 0;
      while (true) { const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } }
    return top; }
}

function networkDelayTime(times, n, k) {
  const adj = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u].push([v, w]);
  const dist = new Array(n + 1).fill(Infinity);
  const heap = new MinHeap((a, b) => a[0] < b[0]);
  heap.push([0, k]);
  while (heap.size) { // Dijkstra
    const [d, u] = heap.pop();
    if (dist[u] !== Infinity) continue;
    dist[u] = d;
    for (const [v, w] of adj[u]) if (dist[v] === Infinity) heap.push([d + w, v]);
  }
  let best = 0;
  for (let i = 1; i <= n; i++) { if (dist[i] === Infinity) return -1; best = Math.max(best, dist[i]); }
  return best;
}