> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Network Delay Time Python Solution with Tests

> Tested Python solution for LeetCode 743 with 13 pytest cases. Generate a practice environment with lcpy.

LeetCode 743, Medium. Topics: Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Shortest Path. [View on LeetCode](https://leetcode.com/problems/network-delay-time/description/).

Generate this problem as a practice environment: tested reference solution, 13 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 743   # by problem number
lcpy gen -s network_delay_time   # by problem name
```

## Problem

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

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

### Examples

![Example 1](https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png)

```
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 = 1
Output: 1
```

```
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
```

### Constraints

* 1 \<= k \<= n \<= 100
* 1 \<= times.length \<= 6000
* times\[i].length == 3
* 1 \<= u\<sub>i\</sub>, v\<sub>i\</sub> \<= n
* u\<sub>i\</sub> != v\<sub>i\</sub>
* 0 \<= w\<sub>i\</sub> \<= 100
* All the pairs (u\<sub>i\</sub>, v\<sub>i\</sub>) are **unique**. (i.e., no multiple edges.)

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/network_delay_time/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/network_delay_time/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(E log V) where E = edges, V = nodes
    # Space: O(V + E)
    def network_delay_time(self, times: list[list[int]], n: int, k: int) -> int:
        # Build adjacency list (1-indexed)
        graph: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
        for source, target, weight in times:
            graph[source].append((target, weight))

        # Dijkstra from source k
        distances: list[int | float] = [float("inf")] * (n + 1)
        distances[k] = 0
        min_heap: list[tuple[int, int]] = [(0, k)]  # (time, node)

        while min_heap:
            time, node = heapq.heappop(min_heap)
            if time > distances[node]:
                continue
            for neighbor, weight in graph[node]:
                arrival = time + weight
                if arrival < distances[neighbor]:
                    distances[neighbor] = arrival
                    heapq.heappush(min_heap, (arrival, neighbor))

        max_time = max(distances[1:])
        return int(max_time) if max_time != float("inf") else -1
```

## Complexity

| Time                                  | Space    |
| ------------------------------------- | -------- |
| O(E log V) where E = edges, V = nodes | O(V + E) |

## Tags

[NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).