[C++/LeetCode] Network Delay Time

Daily LeetCoding Challenge May, Day 14

 

문제: 최장 거리 판별하기

 

아이디어: Dijkstra

신호가 전달되는 시간은 가장 긴 시간에 의해 영향 받는다. 따라서 시작 노드부터 다른 노드까지의 최단 거리를 구하고, 그 중 가중치가 가장 큰 값이 바로 Delay Time이 된다.

 

 

완성

submission: 120ms / 39.8MB

 

class Solution {
public:
    void dikjstra(vector<pair<int, int>> graph[], vector<int> &dist, int start)
    {
    	// 우선 순위 큐 사용
        priority_queue<pair<int, int>> q;
        
        // 시작 노드를 넣고 이때의 가중치는 0이다. 시작 노드의 거리는 0으로 초기화
        q.push({0, start});
        dist[start] = 0;
        
        while (!q.empty())
        {
            int weight = q.top().first * -1;
            int now = q.top().second;
            
            q.pop();
            
            // 거리가 현재보다 크면 진행하지 않는다.
            if (dist[now] < weight)
                continue;
            
            for(int i = 0;i < graph[now].size();i++)
            {
           		// 현재 노드까지의 값이 가중치보다 작은 경우에는 값을 바꾼다.
                int temp = weight + graph[now][i].second;
                
                if (temp < dist[graph[now][i].first])
                {
                    dist[graph[now][i].first] = temp;
                    q.push({temp * -1, graph[now][i].first});
                }
            }
        }
    }
    
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        
        vector<pair<int, int>> graph[n + 1];
        
        for(int i = 0;i < times.size();i++)
            graph[times[i][0]].push_back({times[i][1], times[i][2]});
        
        vector<int> dist(n + 1);
        for(int i = 1;i <= n;i++)
            dist[i] = 1e9;
        
         dikjstra(graph, dist, k);
        
        // 최단 거리 중 가장 큰 값을 선택한다.
        int max = -1;
        for(int i = 1;i <= n;i++)
        {
            if (max < dist[i])
                max = dist[i];
        }
        
        // 최단 거리를 구할 수 없는 경우 -1을 출력한다.
        if (max == 1e9)
            return -1;
        else
            return max;
    }
};