Network Delay Time

Medium· Dijkstra· Shortest Path

Problem

A network has n nodes labelled 1 to n and directed weighted edges times[i] = [u, v, w], meaning a signal takes w time to travel from u to v. A signal is sent from node k. Return how long it takes for every node to receive 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 = 2

Output: -1

Node 2 has no outgoing edges, so node 1 is never reached.

Constraints

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• 0 <= w <= 100

Hints & approach

Hint 1

The time a node receives the signal is its shortest-path distance from k.

Hint 2

All weights are non-negative, which is exactly when Dijkstra applies.

Hint 3

The answer is the largest of those shortest distances.

Approachtry the hints first

Build an adjacency list and run Dijkstra from k with a min-heap of (distance, node). Pop the closest unsettled node, record its final distance, and push each neighbour with the accumulated distance. Skip nodes that are already settled. If fewer than n nodes are settled return -1, otherwise return the maximum settled distance.

Time O(E log V) · Space O(V + E)

← PreviousRedundant Connection Next →Min Cost to Connect All Points