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:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2 Output: 2
Note:
N
will be in the range[1, 100]
.K
will be in the range[1, N]
.- The length of
times
will be in the range[1, 6000]
. - All edges
times[i] = (u, v, w)
will have1 <= u, v <= N
and0 <= w <= 100
.
Related Topics:
Heap, Depth-first Search, Breadth-first Search, Graph
// OJ: https://leetcode.com/problems/network-delay-time/
// Author: github.com/lzl124631x
// Time: O(E + VlogV)
// Space: O(E)
class Solution {
typedef pair<int, int> iPair;
typedef unordered_map<int, vector<iPair>> Graph;
vector<int> dijkstra(Graph &graph, int N, int source) {
priority_queue<iPair, vector<iPair>, greater<>> pq;
vector<int> dist(N, INT_MAX);
pq.emplace(0, source);
dist[source] = 0;
while (pq.size()) {
auto [w, u] = pq.top();
pq.pop();
if (w > dist[u]) continue;
for (auto &[v, c] : graph[u]) {
if (dist[v] > w + c) {
dist[v] = w + c;
pq.emplace(dist[v], v);
}
}
}
return dist;
}
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
Graph graph;
for (auto e : times) graph[e[0] - 1].emplace_back(e[1] - 1, e[2]);
auto dist = dijkstra(graph, N, K - 1);
int mx = *max_element(begin(dist), end(dist));
return mx == INT_MAX ? -1 : mx;
}
};
// OJ: https://leetcode.com/problems/network-delay-time/
// Author: github.com/lzl124631x
// Time: O(VE)
// Space: O(V)
class Solution {
vector<int> bellmanFord(vector<vector<int>>& edges, int V, int src) {
vector<int> dist(V, INT_MAX);
dist[src - 1] = 0;
for (int i = 1; i < V; ++i) {
for (auto &e : edges) {
int u = e[0] - 1, v = e[1] - 1, w = e[2];
if (dist[u] == INT_MAX) continue;
dist[v] = min(dist[v], dist[u] + w);
}
}
return dist;
}
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
auto dist = bellmanFord(times, N, K);
int ans = *max_element(dist.begin(), dist.end());
return ans == INT_MAX ? -1 : ans;
}
};