The problem
A network has n nodes, numbered 1 to n. Each [u, v, w] in times means a signal sent from u reaches v after w time units (one way).
A signal starts at node k. Return how long until every node has received it, or −1 if some node never does.
Examples
- Input
times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2
- Output
2
- Input
times = [[1, 2, 1]], n = 2, k = 1
- Output
1
- Input
times = [[1, 2, 1]], n = 2, k = 2
- Output
-1
Constraints
- 1 ≤ k ≤ n ≤ 100
- 1 ≤ times.length ≤ 6000
- 0 ≤ w ≤ 100, and no pair (u, v) repeats.
The idea
Each node hears the signal at the length of its shortest path from k; the answer is the longest of those.
Dijkstra’s algorithm finds shortest paths when no weight is negative. Keep a min-heap of (arrival time, node). The earliest entry is final — any other route would pass through a later node first, and times only add up. Settle it, and offer its neighbours their arrival times through it. Entries for nodes already settled are stale and skipped.
- Time
- O(E log E)
- Space
- O(n + E)
Solution · every language run against every case
class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: out_of = defaultdict(list) for u, v, w in times: out_of[u].append((v, w)) # Dijkstra: always settle the unsettled node the signal reaches soonest. arrive = {} heap = [(0, k)] while heap: t, u = heappop(heap) if u in arrive: continue # settled already, by a quicker route arrive[u] = t for v, w in out_of[u]: if v not in arrive: heappush(heap, (t + w, v)) return max(arrive.values()) if len(arrive) == n else -1