Network Delay Time

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

import (
    "container/heap"
    "math"
)

type ndtItem struct{ dist, node int }
type ndtPQ []ndtItem

func (h ndtPQ) Len() int            { return len(h) }
func (h ndtPQ) Less(i, j int) bool  { return h[i].dist < h[j].dist }
func (h ndtPQ) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *ndtPQ) Push(x interface{}) { *h = append(*h, x.(ndtItem)) }
func (h *ndtPQ) Pop() interface{}   { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }

func networkDelayTime(times [][]int, n int, k int) int {
    adj := make([][][2]int, n+1)
    for _, e := range times {
        adj[e[0]] = append(adj[e[0]], [2]int{e[1], e[2]})
    }
    dist := make([]int, n+1)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[k] = 0
    pq := &ndtPQ{{0, k}}
    heap.Init(pq)
    for pq.Len() > 0 {
        cur := heap.Pop(pq).(ndtItem)
        if cur.dist > dist[cur.node] {
            continue
        }
        for _, e := range adj[cur.node] {
            v, w := e[0], e[1]
            if cur.dist+w < dist[v] {
                dist[v] = cur.dist + w
                heap.Push(pq, ndtItem{dist[v], v})
            }
        }
    }
    ans := 0
    for i := 1; i <= n; i++ {
        if dist[i] == math.MaxInt32 {
            return -1
        }
        if dist[i] > ans {
            ans = dist[i]
        }
    }
    return ans
}

import heapq
from collections import defaultdict
from typing import List

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        adj: dict[int, list[tuple[int, int]]] = defaultdict(list)
        for u, v, w in times:
            adj[u].append((v, w))
        dist = [float('inf')] * (n + 1)
        dist[k] = 0
        pq: list[tuple[int, int]] = [(0, k)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(pq, (dist[v], v))
        ans = 0
        for i in range(1, n + 1):
            if dist[i] == float('inf'):
                return -1
            ans = max(ans, dist[i])
        return ans

class MinHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0, n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l][0] < this.h[s][0]) s = l;
                if (r < n && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[i], this.h[s]] = [this.h[s], this.h[i]];
                i = s;
            }
        }
        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);
    dist[k] = 0;
    const pq = new MinHeap();
    pq.push([0, k]);
    while (pq.size()) {
        const [d, u] = pq.pop();
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push([dist[v], v]);
            }
        }
    }
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        ans = Math.max(ans, dist[i]);
    }
    return ans;
}

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] adj = new List[n + 1];
        for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
        for (int[] e : times) adj[e[0]].add(new int[]{e[1], e[2]});
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, k});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], u = cur[1];
            if (d > dist[u]) continue;
            for (int[] e : adj[u]) {
                int v = e[0], w = e[1];
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }
}

class MinHeap {
    private h: [number, number][] = [];
    size(): number { return this.h.length; }
    push(v: [number, number]): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): [number, number] {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l][0] < this.h[s][0]) s = l;
                if (r < n && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[i], this.h[s]] = [this.h[s], this.h[i]];
                i = s;
            }
        }
        return top;
    }
}

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