프로그래머스 - 배달

프로그래머스 - 배달

다익스트라를 사용해서 1에서부터 다른 노드까지의 최단 거리를 구한 뒤 그 거리가 K 이하인 곳의 갯수를 세면 된다.

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

using namespace std;

#define pii pair<int, int>
#define INF (1 << 30)

vector<vector<pii>> graph;
vector<int> cost;


int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;
    
    graph.resize(N + 1);
    for(auto it : road) {
        graph[it[0]].push_back( {it[1], it[2]} );
        graph[it[1]].push_back( {it[0], it[2]} );
    }
    
    cost.resize(N + 1, INF);
    cost[1] = 0;
    
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push( { 0, 1 } );
    
    while(1) {
        if(pq.empty())
            break;
        
        pii cur = pq.top(); pq.pop();
        
        if(cur.first > cost[cur.second])
            continue;
        
        for(auto it : graph[cur.second]) {
            int target_node = it.first;
            int target_cost = it.second;
            if(cost[target_node] > target_cost + cur.first) {
                cost[target_node] = target_cost + cur.first;
                pq.push( {cost[target_node], target_node} );
            }
        }
    }
    for(int i=1;i<=N;i++) 
        if(cost[i] <= K) 
            answer++;
    
    return answer;
}