dsa · medium

Network Delay Time (Dijkstra)

GreyOrangeGraphHeap

times[i] = [u, v, w] is a directed weighted edge. n nodes labeled 1..n. Send a signal from node k. Return the time for all nodes to receive it, or -1.

Arguments

• times — directed edges [u, v, w] (from, to, weight)
• n — number of nodes, labeled 1..n
• k — the node that sends the signal (a label in 1..n)

**This is Dijkstra.** Uses the heap + BFS-on-graphs pieces above.

**Example:** times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2 → 2.

Constraints

1 <= n <= 100, 1 <= times.length <= n*(n-1) Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[[2,1,1],[2,3,1],[3,4,1]]
4
2

Expected:
2

Example 2

Input:
[[1,2,1]]
2
1

Expected:
1

Open in the Dojo editor