# Network Delay Time Problem

## Description

LeetCode Problem 743.

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_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i 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 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:

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

Example 2:

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

Example 3:

``````1
2
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_i, v_i <= n
• u_i != v_i
• 0 <= w_i <= 100
• All the pairs (u_i, v_i) are unique. (i.e., no multiple edges.)

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
for (int i = 0; i < times.size(); i++)

vector<int> dist(n+1, INT_MAX);
queue<int> q;
q.push(k);
dist[k] = 0;

while (!q.empty()) {
int t = q.front();
q.pop();
for (pair<int,int> it : adj[t]) {
if (dist[it.first] > dist[t] + it.second) {
dist[it.first] = dist[t] + it.second;
q.push(it.first);
}
}
}

int res = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == INT_MAX)
return -1;
res = max(res, dist[i]);
}
return res;
}
};
``````