프로그래머스 : 배달 (C++, Lv.2, 다익스트라)

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

코딩테스트 연습 - 배달

다익스트라에 대해 공부하고 조금 이따가 풀었는데 그새 까먹어서 푸는데 애좀 먹었다...

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

 

 

소스코드

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

using namespace std;
int a, b ,c, d;
int solution(int N, vector<vector<int> > road, int K) {
    vector <int> w(N+1,1312312);
    int answer = 0;
    //인접리스트 <노드, 거리>
    vector<vector<pair<int,int> > > v(N+1);
    queue<pair<int,int>> q;
    pair<int, int> p;
    for(int i = 0; i < road.size(); i++) {
        //노드1, 노드2, 가중치
        a = road[i][0];
        b = road[i][1];
        c = road[i][2];
        // v[a].push_back({b,c});
        // v[b].push_back({a,c});
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    
    q.push(make_pair(1,0));
    w[1] = 0;
    
    while(!q.empty()) {
        p = q.front();
        //현 노드, 현 가중치
        a = p.first;
        b = p.second;
        q.pop();
        for(int i = 0; i < v[a].size(); i++) {
            c = v[a][i].first;
            d = v[a][i].second;
            //이미 더 작으면 넘기기
            if(w[c] < w[a]+d) continue;
            //가중치 바꾸기
            w[c] = w[a]+d;
            q.push(make_pair(c, w[c]));
            //q.push({v[a][0], w[v[a][0]]});
        }
    }
    
    for(int i = 1; i <= N ; i++) {
        if(w[i]<=K) answer++;
    }
    
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    //cout << "Hello Cpp" << endl;

    return answer;
}