[프로그래머스][Level2] 배달 c++

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

프로그래머스

 

풀이 과정

다익스트라 알고리즘의 기본 문제이다.  
양방향으로 통행할 수 있다고 했으니 시작 -> 도착, 도착 -> 시작 둘 다 연결해준다.

 

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

const int INF = 1e9;
vector<int> dist;
vector<pair<int, int>> edge[51];
priority_queue<pair<int, int>> pq; // 가중치, 정점

void dijkstra(int n){
    dist.resize(n + 1, INF);
    dist[1] = 0;
    pq.push({0, 1});

    while(!pq.empty()){
        int cost = -pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if(dist[now] < cost) continue;
        for(int i = 0; i < edge[now].size(); i++){
            int next = edge[now][i].first;
            int nextcost = edge[now][i].second;

            if(dist[next] > dist[now] + nextcost){
                dist[next] = dist[now] + nextcost;
                pq.push({-dist[next], next});
            }
        }
    }
}

int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;

    for(int i = 0; i < road.size(); i++){
        edge[road[i][0]].push_back({road[i][1], road[i][2]}); // 도착 정점, 가중치
        edge[road[i][1]].push_back({road[i][0], road[i][2]});
    }
    dijkstra(N);

    for(int i = 1; i <= N; i++){
        if(dist[i] <= K) answer++;
    }
    return answer;
}