[C++] 배달 - 다익스트라로 구현 (각 거리의 최소 비용 구하기 - 우선순위큐)

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

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// 1번 마을 부터 K시간 이하로 음식을 배달 할 수 있는 경우의 수
int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    int INF = 1e9;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    vector<vector<int>> maps(N+1,vector<int>(N+1,INF));
    vector<int> dist(N+1,INF);
    for(auto r:road){
        int start = r[0];
        int end = r[1];
        int time = r[2];
        
        maps[start][end] = min(maps[start][end], time);
        maps[end][start] = min(maps[end][start],time);
    }
    
    int cnt = 0;
    
    dist[1] = 0; // dist 는 1에서 각각 노드에 걸리는 최소 거리를 담는 것
    pq.push({0,1}); // cost, node 
    
    while (!pq.empty()){
        int cost = pq.top().first;
        int node = pq.top().second;
        
        pq.pop();
        
        if (cost > dist[node]){
            continue;
        }
        for (int i = 1; i < N+1; i++){
            if (maps[node][i] == INF){
                continue;
            }
            int new_cost = cost + maps[node][i]; // 현재 노드까지 왔을때 cost 갱신
            if (new_cost < dist[i]){ // 기록된 cost 와 비교
                dist[i] = new_cost;
            }
            pq.push({new_cost,i});
        }
        
    }
    
    for (int d: dist){
        if (d <= K){
            answer+= 1;
        }
    }
    return answer;
}