238. Network Delay Time
You are given a directed weighted graph representing a communication network with n nodes, numbered from 1 … n.
The graph is provided as an edge list times, where each record is of the form (ui, vi, wi) where,
- ui — the source node of the directed edge
- vi — the target node of the directed edge
- wi — the time it takes for a signal to travel from ui to vi (non-negative and integer)
A single signal is injected at node k at time 0.
The signal propagates 1-way along the directed edges; whenever it reaches a node, that node immediately retransmits the signal to all of its outgoing neighbors, each traversal taking exactly the edge’s weight wi units of time.
Return the minimum time required for every node in the network to receive the signal.
If some node is unreachable, return -1.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation:
2 →1 (1 unit) 2 →3 (1 unit) →4 ( +1 unit )
The last node (4) gets the signal at time 2.
Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Explanation:
- Direct edge 1 → 2 delivers the signal in 1 unit of time.
Now Your Turn!
Pick the correct output for the given inputInput: times = [[1,2,1]], n = 2, k = 2
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= ui, vi <= n, with ui != vi
- 0 <= wi <= 100
- Every ordered pair (ui, vi) appears at most once in times (no parallel edges).