프로그래머스) Lv3 - 배달

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

한 정점에서 모든 정점으로 가는 최단거리를 구하기 위해 다익스트라(Dijkstra) 알고리즘을 사용해 풀이하였습니다.

 O(logN)의 힙 구조를 가진 우선순위 큐를 사용하여 다익스트라 알고리즘을 구현하였습니다.

---

C++ 소스 코드

#include <vector>
#include <queue>
#define MAX 10000000
using namespace std;
int res[51];
vector<pair<int, int> > adj[51];
int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    fill(&res[0],&res[50]+1,MAX);
    priority_queue<pair<int, int> > pq;
    for(int i=0;i<road.size();i++){
        adj[road[i][0]].push_back(make_pair(road[i][1],road[i][2]));
        adj[road[i][1]].push_back(make_pair(road[i][0],road[i][2]));
        
    }
    res[1]=0;
    pq.push(make_pair(0,1));
    while(!pq.empty()){
        int now = pq.top().second;
        int dist = -pq.top().first;
        pq.pop();
        if (dist > res[now]) continue;
        for(int i=0;i<adj[now].size();i++){
            int next= adj[now][i].first;
            int nextDist = dist + adj[now][i].second;
            if(nextDist < res[next]){
                res[next] = nextDist;
                pq.push(make_pair(-nextDist,next));
            }
        }
    }
    for(int i=1;i<=N;i++){
        if (res[i]<=K) answer++;
    }
    return answer;
}