## Algorithm

Problem Name: 743. Network Delay Time

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] = (ui, vi, wi)`, where `ui` is the source node, `vi` is the target node, and `wi` 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`.

Example 1:

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

Example 2:

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

Example 3:

```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 <= ui, vi <= n`
• `ui != vi`
• `0 <= wi <= 100`
• All the pairs `(ui, vi)` are unique. (i.e., no multiple edges.)

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map();
for (int[] time : times) {
map.computeIfAbsent(time[0], j -> new ArrayList<>()).add(new TimeNode(time[1], time[2]));
}
PriorityQueue < TimeNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.time));
int maxTime = 0;
Set < Integer> visited = new HashSet<>();
while (!pq.isEmpty() && visited.size()  <  n) {
TimeNode removed = pq.remove();
maxTime = Math.max(maxTime, removed.time);
for (TimeNode conn : map.getOrDefault(removed.node, new ArrayList < >())) {
if (visited.contains(conn.node)) {
continue;
}
}
}
return visited.size() == n ? maxTime : -1;
}

class TimeNode {
int node;
int time;

public TimeNode(int node, int time) {
this.node = node;
this.time = time;
}
}
}
``````
Copy The Code &

Input

cmd
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Output

cmd
2

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const networkDelayTime = function(times, n, k) {
const graph = {}
for(const [u, v, w] of times) {
if(graph[u] == null) graph[u] = []
graph[u][v] = w
}
const visited = new Array(n + 1).fill(false)
const pq = new PQ((a, b) => a[0] < b[0])
pq.push([0, k])
let res = 0
while(!pq.isEmpty()) {
const [dist, cur] = pq.pop()
if(visited[cur]) continue
visited[cur] = true
n--
res = dist
if(graph[cur]) {
for(const nxt of Object.keys(graph[cur])) {
pq.push([res + graph[cur][nxt], nxt])
}
}
}
return n === 0 ? res : -1
};

class PQ {
constructor(comparator = (a, b> => a > b) {
this.heap = []
this.top = 0
this.comparator = comparator
}
size() {
return this.heap.length
}
isEmpty() {
return this.size() === 0
}
peek() {
return this.heap[this.top]
}
push(...values) {
values.forEach((value) => {
this.heap.push(value)
this.siftUp()
})
return this.size()
}
pop() {
const poppedValue = this.peek()
const bottom = this.size() - 1
if (bottom > this.top) {
this.swap(this.top, bottom)
}
this.heap.pop()
this.siftDown()
return poppedValue
}
replace(value) {
const replacedValue = this.peek()
this.heap[this.top] = value
this.siftDown()
return replacedValue
}

parent = (i) => ((i + 1) >>> 1) - 1
left = (i) => (i << 1) + 1
right = (i) => (i + 1) << 1
greater = (i, j) => this.comparator(this.heap[i], this.heap[j])
swap = (i, j) => ([this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]])
siftUp = () => {
let node = this.size() - 1
while (node > this.top && this.greater(node, this.parent(node))) {
this.swap(node, this.parent(node))
node = this.parent(node)
}
}
siftDown = () => {
let node = this.top
while (
(this.left(node) < this.size() && this.greater(this.left(node), node)) ||
(this.right(node) < this.size() && this.greater(this.right(node), node))
) {
let maxChild =
this.right(node) < this.size() &&
this.greater(this.right(node), this.left(node))
? this.right(node)
: this.left(node)
this.swap(node, maxChild)
node = maxChild
}
}
}
``````
Copy The Code &

Input

cmd
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Output

cmd
2

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def networkDelayTime(self, times, N, K):
q, t, adj = [(0, K)], {}, collections.defaultdict(list)
for u, v, w in times:
while q:
time, node = heapq.heappop(q)
if node not in t:
t[node] = time
heapq.heappush(q, (time + w, v))
return max(t.values()) if len(t) == N else -1
``````
Copy The Code &

Input

cmd
times = [[1,2,1]], n = 2, k = 1

Output

cmd
1

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0743_NetworkDelayTime
{
public int NetworkDelayTime(int[][] times, int N, int K)
{
var graph = new Dictionary < int, List());
}

var pq = new MinPriorityQueue();
pq.Insert(new Node(0, K));

var distances = new Dictionary < int, int>();

while (pq.Size() > 0)
{
var node = pq.DeleteMin();
if (distances.ContainsKey(node.Target)) continue;

if (graph.ContainsKey(node.Target))
foreach (var edge in graph[node.Target])
if (!distances.ContainsKey(edge.Target))
pq.Insert(new Node(node.Distance + edge.Distance, edge.Target));
}

if (distances.Count != N) return -1;
return distances.Values.Max();
}

public class Node : IComparable < Node>
{
public Node(int distance, int target)
{
Distance = distance;
Target = target;
}

public int Distance { get; set; }
public int Target { get; set; }

public int CompareTo(Node other)
{
return Distance.CompareTo(other.Distance);
}
}

public class MinPriorityQueue : PriorityQueue
{
public MinPriorityQueue() : base() { }

public MinPriorityQueue(int initCapacity) : base(initCapacity) { }

protected override void Sink(int k)
{
while (2 * k  < = N)
{
int j = 2 * k;
if (j < N && pq[j].CompareTo(pq[j + 1]) > 0) j++;
if (pq[k].CompareTo(pq[j])  < = 0) break;
Swap(k, j);
k = j;
}
}

protected override void Swim(int k)
{
while (k > 1 && pq[k / 2].CompareTo(pq[k]) > 0)
{
Swap(k / 2, k);
k = k / 2;
}
}

public Node Min() => First();

public Node DeleteMin() => Delete();
}

public abstract class PriorityQueue
{
protected int N;
protected Node[] pq;

public PriorityQueue() : this(1) { }

public PriorityQueue(int initCapacity)
{
this.N = 0;
pq = new Node[initCapacity + 1];
}

public bool IsEmpty() => N == 0;

public int Size() => N;

public Node First()
{
if (IsEmpty()) { throw new ArgumentOutOfRangeException(); }
return pq[1];
}

public void Insert(Node x)
{
if (N >= pq.Length - 1)
Resize(pq.Length * 2);

pq[++N] = x;
Swim(N);
}

protected abstract void Swim(int k);

public Node Delete()
{
var result = pq[1];
Swap(1, N--);
Sink(1);
pq[N + 1] = null;
if (N > 0 && N == (pq.Length - 1) / 4)
Resize(pq.Length / 2);

return result;
}

protected abstract void Sink(int k);

private void Resize(int newCapacity)
{
var temp = new Node[newCapacity + 1];
for (int i = 1; i  < = N; i++)
temp[i] = pq[i];

pq = temp;
}

protected void Swap(int index1, int index2)
{
var temp = pq[index1];
pq[index1] = pq[index2];
pq[index2] = temp;
}
}
}
}
``````
Copy The Code &

Input

cmd
times = [[1,2,1]], n = 2, k = 1

Output

cmd
1