Network Delay Time

Compute the minimum time for a signal to reach all nodes in a weighted directed network.

dijkstra shortest-path graph heapq

You are given a network of `n` nodes labeled from `1` to `n`. You are also given a list `times` of directed edges, where each element is `[u, v, w]` and represents a directed edge from node `u` to node `v` with a travel time of `w` milliseconds. The signal starts at a given node `k` and travels along the edges.

Write a function `network_delay_time(times, n, k)` that returns the minimum time (in milliseconds) required for the signal to reach **all** `n` nodes. If it is impossible for the signal to reach every node, return `-1`.

**Input:**
- `times`: a list of integer triples `[u, v, w]` (1-indexed nodes).
- `n`: total number of nodes (1 ≤ n ≤ 100).
- `k`: starting node (1 ≤ k ≤ n).

**Output:**
- An integer: the minimum time to reach all nodes, or `-1` if some node is unreachable.

Constraints

≤ n ≤ 100
≤ len(times) ≤ n*(n-1)/2 (but all edges are given; graph may not be complete)
≤ u, v ≤ n, u ≠ v
≤ w ≤ 100
You may assume there are no parallel edges between the same pair of nodes, but the graph may have cycles. The signal travels simultaneously along all available edges.

Example

>>> network_delay_time([[2,1,1],[2,3,1],[3,4,1]], 4, 2)
2
>>> network_delay_time([[1,2,1]], 2, 1)
1
>>> network_delay_time([[1,2,1]], 2, 2)
-1

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of this as a single-source shortest path problem where you need the maximum distance from the source to any reachable node.

Dijkstra's algorithm works well because all edge weights are positive.

Use a min-heap to always expand the node with the smallest current distance.

If after running Dijkstra any node has distance infinity, return -1.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.