엔지니어 게시판
LeetCode 솔루션 분류

[5/14] 43. Network Delay Time

컨텐츠 정보

본문

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

관련자료

댓글 3

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님의 댓글

  • 익명
  • 작성일
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;
    }
};

Coffee님의 댓글

  • 익명
  • 작성일
class Solution {
    
    // adj nodes
    Map<Integer, List<Pair<Integer, Integer>>> adjMap = new HashMap<>();
    
    
    public int networkDelayTime(int[][] times, int n, int k) {
        // 2 1 1 = from 2 to 1, 1 second
        // 2 3 1 = from 2 to 3, 1 second
        // 3 4 1 = from 3 to 4, 1 second
        
        // n = total number of nodes
        // k = initial node
        
        for(int[] time : times){
            int from = time[0];
            int to = time[1];
            int timeCost = time[2];
            
            adjMap.putIfAbsent(from, new ArrayList<>());
            adjMap.get(from).add(new Pair(timeCost, to));
        }
        
        int[] vertex = new int[n+1];
        Arrays.fill(vertex, Integer.MAX_VALUE);
        
        dijkstra(vertex, k, n);
        
        int result = Integer.MIN_VALUE;
        for(int i=1; i<=n; i++){
            result = Math.max(result, vertex[i]);
        }
        
        
        
        return result == Integer.MAX_VALUE? -1 : result;
    }
    
    
    private void dijkstra(int[] vertex, int origin, int n){
        Queue<Pair<Integer, Integer>> pq = new PriorityQueue<Pair<Integer,Integer>>(Comparator.comparing(Pair::getKey));
        
        pq.add(new Pair(0, origin));
        
        // init time for starting node = 0
        vertex[origin] = 0;
        
        while(!pq.isEmpty()){
            Pair<Integer, Integer> topPair = pq.remove();
            
            int currNode = topPair.getValue();
            int currNodeTime = topPair.getKey();
            
            if(currNodeTime > vertex[currNode]){
                continue;
            }
            
            if(!adjMap.containsKey(currNode)){
                continue;
            }
            
            // Prepartage the signal
            for(Pair<Integer, Integer> edge: adjMap.get(currNode)){
                int time = edge.getKey();
                int adjNode = edge.getValue();
                
                if(vertex[adjNode] > currNodeTime + time){
                    vertex[adjNode] = currNodeTime + time;
                    pq.add(new Pair(vertex[adjNode], adjNode));
                }
            }
        }
    }
    
}
전체 396 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 177 명
  • 오늘 방문자 3,821 명
  • 어제 방문자 5,332 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,048 명
알림 0