} } int worst = 0; for (int i = 1; i <= n; i++) { if (dist[i] == Integer.MAX_VALUE) return -1; worst = Math.max(worst, dist[i]); } return worst; } } 19:["Graph","Shortest Path","Heap"] 1b:{"input":"[[1,2,2],[1,3,5],[2,3,1],[2,4,4],[3,4,2],[4,5,3],[3,5,7]]\n5\n1","output":"8","explanation":"Public test case for Network Delay Time"} 1a:["$1b"] 1c:{"python":"from typing import List, Optional\n\ndef networkDelayTime(times: List[List[int]], n: int, k: int) -> int:\n pass\n","cpp":"#include \nusing namespace std;\n\nint networkDelayTime(vector>& times, int n, int k) {\n \n}\n","java":"import java.util.*;\n\nclass Solution {\n public int networkDelayTime(int[][] times, int n, int k) {\n \n }\n}\n","javascript":"/**\n * @param {number[][]} times\n * @param {number} n\n * @param {number} k\n * @return {number}\n */\nvar networkDelayTime = function(times, n, k) {\n \n};\n","go":"package main\n\nfunc networkDelayTime(times [][]int, n int, k int) int {\n \n}\n"} 20:T4ea,import java.util.*; class Solution { public int networkDelayTime(int[][] times, int n, int k) { Map> graph = new HashMap<>(); for (int[] t : times) { graph.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 heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); heap.offer(new int[]{0, k}); while (!heap.isEmpty()) { int[] top = heap.poll(); int d = top[0], u = top[1]; if (d > dist[u]) continue; if (graph.containsKey(u)) { for (int[] edge : graph.get(u)) { int v = edge[0], w = edge[1]; int nd = d + w; if (nd < dist[v]) { dist[v] = nd;

293. Network Delay Time

Examples

Constraints