엔지니어 게시판
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 ListShare

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.)

관련자료

댓글 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.
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;
    }
};
전체 85 / 1 페이지
게시글 쓰기
번호
제목
이름

최근글


새댓글


Stats


알림 0