> For the complete documentation index, see [llms.txt](https://twchen.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://twchen.gitbook.io/leetcode/network-delay-time.md).

# Network Delay Time

## Description

There are `N` network nodes, labelled `1` to `N`.

Given `times`, 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 source to target.

Now, we send a signal from a certain node `K`. How long will it take for all nodes to receive the signal? If it is impossible, return `-1`.

**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
```

**Note:**

1. `N` will be in the range `[1, 100]`.
2. `K` will be in the range `[1, N]`.
3. The length of `times` will be in the range `[1, 6000]`.
4. All edges `times[i] = (u, v, w)` will have `1 <= u, v <= N` and `0 <= w <= 100`.

## Solution

This problem is equivalent to the problem of finding the shortest paths between a node and all other nodes.

### Dijkstra's algorithm

Running time: $$O(|E| + |V| \log |V|)$$.

```cpp
class Solution {
public:
    int networkDelayTime(vector<vector<int>> &times, int N, int K) {
        vector<vector<pair<int, int>>> neighbors(N + 1);
        for (auto &t : times)
            neighbors[t[0]].emplace_back(t[1], t[2]);
        vector<int> dist(N + 1, INT_MAX);
        dist[K] = 0;
        auto comp = [&](int a, int b) {
            return dist[a] > dist[b];
        };
        vector<int> heap(N);
        for (int i = 0; i < N; ++i)
            heap[i] = i + 1;
        // Let V be the set of nodes.
        // V - heap is the set of nodes to which the shortest paths from node K are known.
        while (!heap.empty()) {
            // extract min
            make_heap(heap.begin(), heap.end(), comp);
            int u = heap.front();
            heap.front() = heap.back();
            heap.pop_back();
            // the closest node is unreachable
            if (dist[u] == INT_MAX)
                return -1;
            for (auto &p : neighbors[u]) {
                int v = p.first;
                int w = p.second;
                // O(1) time decrease key
                dist[v] = min(dist[v], dist[u] + w);
            }
        }
        return *max_element(dist.begin() + 1, dist.end());
    }
};
```