LeetCode 솔루션 분류
[5/14] 43. Network Delay Time
작성자 정보
- mingki 작성
- 작성일
본문
[LeetCode 시즌 3] 2022년 5월 14일 문제입니다.
https://leetcode.com/problems/network-delay-time/
743. Network Delay Time
Medium
4277285Add to ListShareYou 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.)
관련자료
-
링크
댓글 2
austin님의 댓글
- austin
- 작성일
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
int ret = 0;
typedef tuple<int, int> edge;
unordered_set<int> s;
priority_queue<edge, vector<edge>, greater<edge>> q;
vector<vector<edge>> v(n+1);
for(auto &t : times) v[t[0]].emplace_back(t[2], t[1]);
q.emplace(0, k);
while(s.size() != n && !q.empty()) {
auto [time, node] = q.top();
q.pop();
if (s.find(node) != s.end()) continue;
ret = time;
s.emplace(node);
for(auto [delta, next_node] : v[node]) if (s.find(next_node) == s.end()) q.emplace(time + delta, next_node);
}
return s.size() == n ? ret : -1;
}
};
mingki님의 댓글
- mingki
- 작성일
C++
Runtime: 173 ms, faster than 45.79% of C++ online submissions for Network Delay Time.
Memory Usage: 48.7 MB, less than 11.84% of C++ online submissions for Network Delay Time.
Runtime: 173 ms, faster than 45.79% of C++ online submissions for Network Delay Time.
Memory Usage: 48.7 MB, less than 11.84% of C++ online submissions for Network Delay Time.
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<int> visited(n + 1, 1e9);
vector<vector<vector<int>>> edges(n + 1);
stack<int> st;
for (auto &time : times) {
edges[time[0]].push_back({time[1], time[2]});
}
st.push(k);
visited[k] = 0;
while (!st.empty()) {
int curr = st.top(); st.pop();
for (auto &edge : edges[curr]) {
if (visited[edge[0]] > visited[curr] + edge[1]) {
visited[edge[0]] = visited[curr] + edge[1];
st.push(edge[0]);
}
}
}
int result = 0;
for (int i = 1; i < visited.size(); ++i) {
result = max(result, visited[i]);
}
return result == 1e9 ? -1 : result;
}
};