[LeetCode] C++ 743. Network Delay Time

https://leetcode.com/problems/network-delay-time/description/

 

문제

 

문제 분석

- 네트워크 중에서 모든 노드를 탐색하는 것이기 때문에 다익스트라로 검색 후, 가장 먼 거리에 떨어져있는 노드와의 거리를 반환하면 됩니다. (모든 노드를 탐지하는데 걸리는 총 시간이 아닙니다. 네트워크이기에 동시에 퍼져나간다는 가정 후, 가장 먼 노드까지 다 도달하는데 총 얼마나 걸리는가를 묻고 있는 것입니다.)

- 초기 노드에서 출발 시 도착못하는 경우 -1를 반환하면 됩니다.

 

풀이

#include <vector>
#include <queue>
#include <limits>
#include <utility>

using namespace std;

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, int>>> graph(n + 1);
        for (const auto& time : times) {
            graph[time[0]].emplace_back(time[1], time[2]);
        }
        
        vector<int> dist(n + 1, numeric_limits<int>::max());
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.emplace(0, k);
        dist[k] = 0;
        
        while (!pq.empty()) {
            int current_dist = pq.top().first;
            int current_node = pq.top().second;
            pq.pop();
            
            if (current_dist > dist[current_node]) {
                continue;
            }
            
            for (const auto& node : graph[current_node]) {
                int next_node = node.first;
                int next_dist = node.second;
                
                if (current_dist + next_dist < dist[next_node]) {
                    dist[next_node] = current_dist + next_dist;
                    pq.emplace(dist[next_node], next_node);
                }
            }
        }
        
        int max_result = 0;
        
        for (int i = 1; i <= n; ++i) {
            if (dist[i] == numeric_limits<int>::max()) {
                return -1;
            }
            max_result = max(max_result, dist[i]);
        }
        
        return max_result;
    }
};