#include <limits.h>
#include <stdlib.h>
typedef struct {
int d, node;
} Item;
typedef struct Edge {
int to, w;
struct Edge *next;
} Edge;
static void swap(Item *a, Item *b) {
Item t = *a;
*a = *b;
*b = t;
}
static void push(Item *heap, int *size, Item x) {
int i = (*size)++;
heap[i] = x;
while (i > 0 && heap[(i - 1) / 2].d > heap[i].d) {
swap(&heap[(i - 1) / 2], &heap[i]);
i = (i - 1) / 2;
}
}
static Item pop(Item *heap, int *size) {
Item top = heap[0];
heap[0] = heap[--(*size)];
int i = 0;
for (;;) {
int s = i, l = 2 * i + 1, r = l + 1;
if (l < *size && heap[l].d < heap[s].d)
s = l;
if (r < *size && heap[r].d < heap[s].d)
s = r;
if (s == i)
break;
swap(&heap[s], &heap[i]);
i = s;
}
return top;
}
int networkDelayTime(int **times, int timesSize, int *timesColSize, int n,
int k) {
(void)timesColSize;
// adjacency lists as linked lists; one edge node per input edge
Edge **adj = calloc(n + 1, sizeof(Edge *));
Edge *pool = malloc(timesSize * sizeof(Edge));
for (int i = 0; i < timesSize; i++) {
pool[i] = (Edge){times[i][1], times[i][2], adj[times[i][0]]};
adj[times[i][0]] = &pool[i];
}
int *dist = malloc((n + 1) * sizeof(int));
for (int i = 0; i <= n; i++)
dist[i] = INT_MAX;
// each successful relaxation pushes once, so at most timesSize + 1 entries
Item *heap = malloc((timesSize + 1) * sizeof(Item));
int size = 0;
dist[k] = 0;
push(heap, &size, (Item){0, k});
while (size > 0) {
Item cur = pop(heap, &size);
if (cur.d > dist[cur.node])
continue; // stale entry
for (Edge *e = adj[cur.node]; e; e = e->next) {
if (cur.d + e->w < dist[e->to]) {
dist[e->to] = cur.d + e->w;
push(heap, &size, (Item){dist[e->to], e->to});
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
if (dist[i] > ans)
ans = dist[i];
free(adj);
free(pool);
free(dist);
free(heap);
return ans == INT_MAX ? -1 : ans;
}
#include <algorithm>
#include <climits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int networkDelayTime(vector<vector<int>> ×, int n, int k) {
vector<vector<pair<int, int>>> adj(n + 1); // node -> {neighbor, weight}
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<>>
pq; // {dist, node}
dist[k] = 0;
pq.push({0, k});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u])
continue; // stale entry
for (auto [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
int ans = *max_element(dist.begin() + 1, dist.end());
return ans == INT_MAX ? -1 : ans;
}
};
package graphs
import "container/heap"
type edge struct{ to, w int }
type item struct{ d, node int }
type minHeap []item
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].d < h[j].d }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any) { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() any {
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([][]edge, n+1) // node -> {neighbor, weight}
for _, t := range times {
adj[t[0]] = append(adj[t[0]], edge{t[1], t[2]})
}
const inf = int(^uint(0) >> 1)
dist := make([]int, n+1)
for i := range dist {
dist[i] = inf
}
dist[k] = 0
pq := &minHeap{{0, k}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(item)
if cur.d > dist[cur.node] {
continue // stale entry
}
for _, e := range adj[cur.node] {
if cur.d+e.w < dist[e.to] {
dist[e.to] = cur.d + e.w
heap.Push(pq, item{dist[e.to], e.to})
}
}
}
ans := 0
for _, d := range dist[1:] {
ans = max(ans, d)
}
if ans == inf {
return -1
}
return ans
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
List<List<int[]>> adj = new ArrayList<>(); // node -> {neighbor, weight}
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[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // {dist, node}
dist[k] = 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; // stale entry
for (int[] e : adj.get(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++)
ans = Math.max(ans, dist[i]);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}
/**
* @param {number[][]} times
* @param {number} n
* @param {number} k
* @return {number}
*/
var networkDelayTime = function (times, n, k) {
const adj = Array.from({ length: n + 1 }, () => []); // node -> [neighbor, weight]
for (const [u, v, w] of times) adj[u].push([v, w]);
const dist = new Array(n + 1).fill(Infinity);
dist[k] = 0;
// binary min-heap of [dist, node]: JS has no built-in priority queue
const heap = [[0, k]];
const push = (item) => {
heap.push(item);
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];
const last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
for (;;) {
let s = i;
const l = 2 * i + 1;
const r = l + 1;
if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
if (s === i) break;
[heap[s], heap[i]] = [heap[i], heap[s]];
i = s;
}
}
return top;
};
while (heap.length > 0) {
const [d, u] = pop();
if (d > dist[u]) continue; // stale entry
for (const [v, w] of adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
push([dist[v], v]);
}
}
}
const ans = Math.max(...dist.slice(1));
return ans === Infinity ? -1 : ans;
};
import heapq
from typing import List
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
adj = [[] for _ in range(n + 1)] # node -> (neighbor, weight)
for u, v, w in times:
adj[u].append((v, w))
dist = [float("inf")] * (n + 1)
dist[k] = 0
pq = [(0, k)] # (dist, node)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # stale entry
for v, w in adj[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
ans = max(dist[1:])
return -1 if ans == float("inf") else ans
use std::cmp::Reverse;
use std::collections::BinaryHeap;
impl Solution {
pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
let n = n as usize;
let mut adj = vec![vec![]; n + 1]; // node -> (neighbor, weight)
for t in × {
adj[t[0] as usize].push((t[1] as usize, t[2]));
}
let mut dist = vec![i32::MAX; n + 1];
let mut pq = BinaryHeap::new(); // Reverse((dist, node)) makes it a min-heap
dist[k as usize] = 0;
pq.push(Reverse((0, k as usize)));
while let Some(Reverse((d, u))) = pq.pop() {
if d > dist[u] {
continue; // stale entry
}
for &(v, w) in &adj[u] {
if d + w < dist[v] {
dist[v] = d + w;
pq.push(Reverse((dist[v], v)));
}
}
}
let ans = *dist[1..].iter().max().unwrap();
if ans == i32::MAX { -1 } else { ans }
}
}