[C++] 프로그래머스 : 등산코스 정하기

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

다익스트라 알고리즘 적용 & 다른 기준으로 비교

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct cmp{
    bool operator()(pair<int,int> a, pair<int,int> b){
        return a.second > b.second;
    }
};

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer;
    
    int d[50001];
    vector<pair<int,int>> G[50001]; // G[from] = {to, weight}
    bool isSummit[50001];
    priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq; // {pos, intensity}
    
    vector<pair<int,int>> res;
    
    for(int i=1; i<=n; i++) d[i] = -1;
    for(int i=0; i<paths.size(); i++){
        G[paths[i][0]].push_back({paths[i][1], paths[i][2]});
        G[paths[i][1]].push_back({paths[i][0], paths[i][2]});
    }
    for(int i=0; i<summits.size(); i++) isSummit[summits[i]] = true;
    for(int i=0; i<gates.size(); i++){
        d[gates[i]] = 0;
        pq.push({gates[i], 0});
    }
    
    while(!pq.empty()){
        int cp = pq.top().first, inten = pq.top().second;
        pq.pop();
        
        if(d[cp] < inten) continue;
        
        if(isSummit[cp]){
            res.push_back({inten, cp});
            continue;
        }
        
        for(int i=0; i<G[cp].size(); i++){
            int np = G[cp][i].first, w = G[cp][i].second;
            
            if(d[np] != -1 && d[np] <= max(inten, w)) continue;
            
            d[np] = max(inten, w);
            pq.push({np, d[np]});
        }
    }
    
    sort(res.begin(), res.end());
    answer.push_back(res[0].second);
    answer.push_back(res[0].first);
    
    return answer;
}