743. Network Delay Time | LeetCode Solution
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 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.)
class Solution
{
public:
int networkDelayTime(vector<vector<int>> ×, int n, int k)
{
int ans = 0;
vector<int> dist(n + 1, INT_MAX);
dist[k] = 0;
vector<vector<pair<int, int>>> graph(n + 1);
for (int i = 0; i < times.size(); i++)
{
graph[times[i][0]].push_back({times[i][1], times[i][2]});
}
set<pair<int, int>> s;
s.insert({0, k});
while (!s.empty())
{
auto x = *(s.begin());
s.erase(x);
for (auto it : graph[x.second])
{
if (dist[it.first] > dist[x.second] + it.second)
{
s.erase({dist[it.first], it.first});
dist[it.first] = dist[x.second] + it.second;
s.insert({dist[it.first], it.first});
}
}
}
for (int i = 1; i <= n; i++)
{
if (dist[i] < INT_MAX)
{
ans = max(ans, dist[i]);
}
else
{
ans = -1;
break;
}
}
return ans;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.