Find how long it takes for a signal sent from one node to reach every node in a directed weighted graph.
Problem
You are given a directed, weighted graph with n nodes labeled from 1 to n. Each directed edge (u, v, w) means a signal can travel from node u to node v in w time units.
A signal starts at node k at time 0. Return the minimum time needed for the signal to reach every node in the graph. If at least one node is unreachable, return -1.
In other words, compute the largest among the shortest travel times from k to all other nodes, or report that not all nodes are reachable.
Input Format
times: a list of directed edges, where each edge is[u, v, w]n: the number of nodesk: the starting node
Output Format
- Return a single integer:
- the time when the last reachable node receives the signal, if every node is reachable
-1if some node cannot be reached fromk
Constraints
1 <= n1 <= k <= n- Each edge contains exactly three integers
[u, v, w] - Edge weights are positive
- Nodes are labeled
1throughn
Hints
- Model the problem as a shortest-path computation from a single source.
- Keep track of the best known time to each node and expand the currently fastest-reachable node first.
- After processing, check whether every node was reached.
Input Format
times: directed weighted edges[[u, v, w], ...]n: number of nodes labeled1..nk: starting node
Output Format
- Integer delay for all nodes to receive the signal, or
-1if some node is unreachable
Constraints
- Graph is directed
- Edge weights are positive
- Nodes are labeled from
1ton - Return
-1if not all nodes are reachable
Example 1
Input
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output
2
Explanation
The signal reaches node 1 at time 1, node 3 at time 1, and node 4 at time 2. The last node receives the signal at time 2.
Example 2
Input
times = [[1,2,1]], n = 2, k = 1
Output
1
Explanation
Node 2 is reached in 1 time unit, so the total delay is 1.
Show 1 more example
Example 3
Input
times = [[1,2,1]], n = 2, k = 2
Output
-1
Explanation
Node 1 cannot be reached from node 2, so not all nodes receive the signal.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.