Network Delay Time
Part of Practice: Shortest & Cheapest
You have a network of n nodes labeled 1 to n, and a list of directed wires times where each entry [u, v, w] means a signal takes w time units to travel from node u to node v. A signal is broadcast from node k. Return the time it takes for every node to receive the signal — that is, the longest of the fastest arrival times. If some node can never receive the signal, return -1.
Constraints that matter: up to 100 nodes, up to 6000 wires, and every travel time is at least 1 (no negative weights), which is exactly the setting where Dijkstra's algorithm applies.
Examples
- Input:
- times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
- Output:
- 2
From node 2, nodes 1 and 3 hear the signal at time 1. Node 4 hears it through node 3 at time 2. The last node to hear it defines the answer.
- Input:
- times = [[1,2,1]], n = 2, k = 1
- Output:
- 1
- Input:
- times = [[1,2,1]], n = 2, k = 2
- Output:
- -1
The only wire points from 1 to 2, so node 1 can never hear a signal sent from node 2.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.