codejump
MediumPro challengePythonJavaScriptTypeScript

Graph — Network Delay Time (Dijkstra)

Data StructuresGraphsDijkstraHeap

solve(times, n, k) — a network has n nodes labelled 1..n. Each
[u, v, w] in times is a directed edge: a signal sent from u reaches v
after w time units. A signal starts at node k.

Return the time it takes for all nodes to receive it, or -1 if some node is
unreachable.

That is the largest shortest-path distance from k. All weights are
non-negative, so Dijkstra's algorithm with a min-heap applies. A MinHeap (ordered
by item[0]) is provided for JavaScript and TypeScript; Python has heapq.

Examples

solve([[2,1,1],[2,3,1],[3,4,1]], 4, 2)     → 2
solve([[1,2,1]], 2, 1)                     → 1
solve([[1,2,1]], 2, 2)                     → -1
solve([[1,2,1],[2,3,2],[1,3,4]], 3, 1)     → 3    // 1→2→3 beats the direct edge

Sample tests

Test #1Classic example
Input: [[[2,1,1],[2,3,1],[3,4,1]],4,2]
Output: 2
Test #2Single edge
Input: [[[1,2,1]],2,1]
Output: 1
Test #3Source cannot reach node 1
Input: [[[1,2,1]],2,2]
Output: -1
← All challenges