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

# Network Delay Time

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

```java
class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // Creating Adjacency List
        ArrayList<int[]>[] graph = new ArrayList[N];
        for (int i = 0; i < N; i++)
            graph[i] = new ArrayList<>();
        for (int[] edge : times)
            graph[edge[0] - 1].add(new int[] { edge[1] - 1, edge[2] });

        // (distance, node) into pq
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        pq.add(new int[] { 0, K - 1 });

        boolean[] visited = new boolean[N];
        int res = 0, coveredNodes = 0;
        while (!pq.isEmpty()) {
            // Picking the Node at shortest Distance
            int[] cur = pq.remove();
            int curDist = cur[0];
            int curNode = cur[1];
            if (visited[curNode])
                continue;
            visited[curNode] = true;
            // The last node in the PQ will have the largest distance already
            res = curDist;
            coveredNodes++;
            for (int[] node : graph[curNode])
                pq.add(new int[] { curDist + node[1], node[0] });
        }
        return coveredNodes == N ? res : -1;
    }
}
```