Railway Network Delay Optimizer

import java.util.*;
class Solution {
    public int optimize_railway_delay(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] t : times) {
            adj.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[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.add(new int[]{0, k});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];
            if (d > dist[u]) continue;
            if (!adj.containsKey(u)) continue;
            for (int[] v : adj.get(u)) {
                if (dist[u] + v[1] < dist[v[0]]) {
                    dist[v[0]] = dist[u] + v[1];
                    pq.add(new int[]{dist[v[0]], v[0]});
                }
            }
        }
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxDist = Math.max(maxDist, dist[i]);
        }
        return maxDist;
    }
}

function optimize_railway_delay(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 = [[0, k]];
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [d, u] = pq.shift();
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([dist[v], v]);
            }
        }
    }
    let maxDist = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        maxDist = Math.max(maxDist, dist[i]);
    }
    return maxDist;
}

function optimize_railway_delay($times, $n, $k) {
    $adj = array_fill(1, $n, []);
    foreach ($times as $t) $adj[$t[0]][] = [$t[1], $t[2]];
    $dist = array_fill(1, $n, INF);
    $dist[$k] = 0;
    $pq = [[0, $k]];
    while (!empty($pq)) {
        usort($pq, function($a, $b) { return $a[0] - $b[0]; });
        $u_data = array_shift($pq);
        $d = $u_data[0]; $u = $u_data[1];
        if ($d > $dist[$u]) continue;
        if (!isset($adj[$u])) continue;
        foreach ($adj[$u] as $v_data) {
            $v = $v_data[0]; $w = $v_data[1];
            if ($dist[$u] + $w < $dist[$v]) {
                $dist[$v] = $dist[$u] + $w;
                $pq[] = [$dist[$v], $v];
            }
        }
    }
    $maxDist = 0;
    for ($i = 1; $i <= $n; $i++) {
        if ($dist[$i] == INF) return -1;
        $maxDist = max($maxDist, $dist[$i]);
    }
    return $maxDist;
}

import heapq
def optimize_railway_delay(times, n, k):
    adj = {i: [] for i in range(1, n + 1)}
    for u, v, w in times:
        adj[u].append((v, w))
    pq = [(0, k)]
    visited = {}
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited: continue
        visited[u] = d
        for v, w in adj[u]:
            if v not in visited:
                heapq.heappush(pq, (d + w, v))
    if len(visited) < n: return -1
    return max(visited.values())

use std::collections::{HashMap, BinaryHeap};
use std::cmp::Ordering;

#[derive(Copy, Clone, Eq, PartialEq)]
struct State { cost: i32, position: i32 }
impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering { other.cost.cmp(&self.cost).then_with(|| self.position.cmp(&other.position)) }
}
impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
}

pub fn optimize_railway_delay(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
    let mut adj = HashMap::new();
    for t in times {
        adj.entry(t[0]).or_insert(Vec::new()).push((t[1], t[2]));
    }
    let mut dist = vec![i32::MAX; (n + 1) as usize];
    dist[k as usize] = 0;
    let mut pq = BinaryHeap::new();
    pq.push(State { cost: 0, position: k });
    while let Some(State { cost, position }) = pq.pop() {
        if cost > dist[position as usize] { continue; }
        if let Some(neighbors) = adj.get(&position) {
            for &(neighbor, weight) in neighbors {
                if dist[position as usize] + weight < dist[neighbor as usize] {
                    dist[neighbor as usize] = dist[position as usize] + weight;
                    pq.push(State { cost: dist[neighbor as usize], position: neighbor });
                }
            }
        }
    }
    let mut max_dist = 0;
    for i in 1..=n {
        let d = dist[i as usize];
        if d == i32::MAX { return -1; }
        max_dist = std::cmp::max(max_dist, d);
    }
    max_dist
}

function optimize_railway_delay(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 = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    const pq: [number, number][] = [[0, k]];
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [d, u] = pq.shift()!;
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([dist[v], v]);
            }
        }
    }
    let maxDist = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        maxDist = Math.max(maxDist, dist[i]);
    }
    return maxDist;
}