[Leetcode,c++] Network Delay Time

문제

Network Delay Time - LeetCode

 

코드

class Solution {
public:
    vector<pair<int,int>>graph[101];
    int d[101];
    
    void dijkstra(int start){
        priority_queue<pair<int,int>>pq;
        pq.push({0,start});
        d[start]=0;
        
        while(!pq.empty()){
            int dist = -pq.top().first;
            int now  = pq.top().second;
            pq.pop();
            if(d[now]<dist) continue;
            
            for(int i=0; i<graph[now].size(); i++){
                int cost = dist + graph[now][i].second;
                int neighbor = graph[now][i].first;
                if(cost<d[neighbor]){
                    d[neighbor] = cost;
                    pq.push({-cost,neighbor});
                }
            }
        }
    }
    
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        for(int i=0; i<times.size(); i++){
            graph[times[i][0]].push_back({times[i][1],times[i][2]});
        }
        
        fill(d,d+101,1e9);
        
        dijkstra(k);
        
        int ans=0;
        
        for(int i=1; i<=n; i++){
            if(d[i]==1e9) return -1;
            else ans=max(ans,d[i]);
        }
        
        return ans;
    }
    
};

 

풀이

dijkstra로 구현했습니다.

위 그래프의 입출력이 아래와 같을 때 출력해야 하는 문제는 스타트 지점(k=2)에서 모든 노드(n=4)까지 가는 데 걸리는 시간을 출력하는 것입니다.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

2에서 1번과 3번까지는 동시에 갈수 있으니 동일하게 1초가 걸린다고 볼 수 있습니다.

for(int i=1; i<=n; i++){
	if(d[i]==1e9) return -1;
	else ans=max(ans,d[i]);
}

코드 마지막의 위 부분을 통해서 해당 노드로 갈 수 없을 때는 바로 -1을 return 하였고, 갈 수 있는 경우에는 max(ans,d[i])를 통해 해당 노드까지 걸리는 최고 시간을 정답으로 갱신해주었습니다.(dijkstra를 실행하면서 출발 노드에서 해당 노드까지 걸리는 시간을 갱신해줬으니)

다만 채점시간이 꽤 오래 걸려서 로직 문제인 줄 알았는데 제출할 때마다 시간이 차이가 나서 그냥 채점 서버 문제인 걸로...