(프로그래머스 c++)배달

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

코딩테스트 연습 - 배달

 

다익스트라를 이용하여 1에서 거리가 K 이하인 마을의 수를 구할 수 있다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    vector<pair<int, int>> graph[51];
    priority_queue<pair<int, int>> pq;
    vector<int> dist(51, 999999);
    
    for(int i = 0; i < road.size(); i++){
        int a, b, c;
        
        a = road[i][0];
        b = road[i][1];
        c = road[i][2];
        
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }
    
    pq.push(make_pair(1, 0));
    dist[1] = 0;
    
    while(!pq.empty()){
        int current = pq.top().first;
        int cost = -pq.top().second;
        
        pq.pop();
        
        for(int i = 0; i < graph[current].size(); i++){
            int next = graph[current][i].first;
            int nextCost = graph[current][i].second;
            
            if(dist[next] > dist[current] + nextCost){
                dist[next] = dist[current] + nextCost;
                pq.push(make_pair(next, -dist[next]));
            }
        }
    }
    
    for(int i = 1; i <= N; i++){
        if(dist[i] <= K){
            answer++;
        }
    }
    
    return answer;
}