LeetCode 솔루션

[5/14] 43. Network Delay Time

mingki 작성
작성일 2022.05.13 23:51

246 조회
2 댓글
목록 게시글 쓰기

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

#LeetCode, #Google, #Amazon, #Microsoft, #Adobe, #ByteDance, #eBay, #Uber, #Akuna Capital, #Depth-First Search(DFS), #Breadth-First Search(BFS), #Graph, #Heap, #Shortest Path

링크

https://leetcode.com/problems/network-delay-time/ 15 회 연결

austin
작성일 05.14 02:49

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
작성일 05.14 23:33

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;
    }
};

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.
[code=C++]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;
    }
};[/code]

로그인한 회원만 댓글 등록이 가능합니다.

목록 게시글 쓰기