[LeetCode] 743. Network Delay Time

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

Network Delay Time - LeetCode

Network Delay Time

 

 

노드에서 노드까지 신호가 전송되는데 걸리는 시간이 나열되어 있다.

이때, k 노드에서 다른 모든 노드로 신호를 보내는데 총 얼마나 걸리는지 묻는 문제이다.

전형적인 다익스트라 문제다.

노드X노드로 그래프를 만든뒤, 다익스트라 알고리즘을 돌려주고,

k 행의 모든 요소를 살펴보고 닿지 않은 곳이 있다면 -1을, 아니라면 max값을 출력해주자.

다익스트라 알고리즘을 잊어 다시 찾아보았다

다익스트라 알고리즘을 확실히 알아놓자.

 

전체 풀이 코드

class Solution {
public:
    struct compare {bool operator()(pair<int, int> a, pair<int, int> b) {return a.second>b.second;}};
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        long G[105][105];
        for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) G[i][j] = i==j?0:INT_MAX;
        for (vector<int> time:times) G[time[0]][time[1]] = time[2];
        priority_queue<pair<int,int>, vector<pair<int,int>>, compare> pq;
        for (int i=1; i<=n; i++) pq.push(make_pair(i,G[k][i]));
        while (!pq.empty()) {
            pair<int, int> p = pq.top();
            pq.pop();
            G[k][p.first] = G[k][p.first]<p.second?G[k][p.first]:p.second;
            for (int i=1; i<=n; i++) if (G[k][i] > G[k][p.first] + G[p.first][i]) {
                G[k][i] = G[k][p.first] + G[p.first][i];
                pq.push(make_pair(i,G[k][i]));
            }
        }
        int ret = 0;
        for (int i=1; i<=n; i++) {
            if(G[k][i]==INT_MAX) return -1;
            else ret = ret>G[k][i]? ret:G[k][i];
        }
        return ret;
    }
};