77. Network Delay Time

Medium · Graph

You are given a network of `n` nodes labeled from `1` to `n`, and a list of travel times as directed edges `times[i] = [u, v, w]`, where `u` is the source node, `v` is the target node, and `w` is the time it takes for a signal to travel from `u` to `v`. You are also given a starting node `k`.

We send a signal from node `k`. Return the **minimum time** it takes for **all** `n` nodes to receive the signal. If it is impossible for all nodes to receive the signal, return `-1`.

This is a classic shortest-path problem. Use Dijkstra's algorithm to find the shortest path from `k` to every other node, then return the maximum of those shortest distances (since all nodes must be reached). If any node is unreachable, return `-1`.

Examples

Example 1
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: Starting from node 2: node 1 is reached at time 1, node 3 at time 1, node 4 at time 2. All 4 nodes are reached; the last one arrives at time 2.
Example 2
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Explanation: Node 1 sends to node 2 in time 1. Both nodes are reached, so the answer is 1.

Constraints