A network has n nodes labelled 1 to n. times[i] = [u, v, w] means a signal sent from u reaches v after w units of time (edges are directed). A signal is sent from node k. Return the time it takes for all nodes to receive it, or -1 if some node can never receive it.
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- 1 <= u, v <= n, u != v
- 0 <= w <= 100
- All (u, v) pairs are unique
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The signal reaches each node along its fastest route, so we need the shortest path from k to every node, and the answer is the maximum of those. Running a DFS over all paths is exponential. Since weights are non-negative, Dijkstra works: always expand the unvisited node with the smallest known distance; at that moment its distance is final, because any other route would go through a node that is already at least as far.
Algorithm
- Build an adjacency list
u -> (v, w). - Push
(0, k)into a min-heap and keep adistmap or array. - Pop the smallest
(d, u); skip it ifuis already finalised. Otherwise recorddist[u] = d. - For each edge
u -> vwith weightw, push(d + w, v)ifvis not finalised. - If all
nnodes are finalised return the maximum distance, else return -1.
O(E log E)Space: O(V + E)class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: adj = defaultdict(list) for u, v, w in times: adj[u].append((v, w)) dist = {} heap = [(0, k)] while heap: d, u = heapq.heappop(heap) if u in dist: continue # already finalised with a smaller distance dist[u] = d for v, w in adj[u]: if v not in dist: heapq.heappush(heap, (d + w, v)) return max(dist.values()) if len(dist) == n else -1