복실

dijkstra.cpp

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

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    int village[51][51];
    int INF = 10000 * 50;
    bool visited[51];
    int D[51];
    for (int i = 1; i <= N; i++) {
        D[i] = INF;
        visited[i] = false;
        for (int j = 1; j <= N; j++) {
            if (i == j) village[i][j] = 0;
            else village[i][j] = INF;
        }
    }
    D[1] = 0;
    visited[1] = true;
    for (int i = 0; i < road.size(); i++) {
        village[road[i][0]][road[i][1]] = village[road[i][0]][road[i][1]] > road[i][2] ? road[i][2] : village[road[i][0]][road[i][1]];
        village[road[i][1]][road[i][0]] = village[road[i][1]][road[i][0]] > road[i][2] ? road[i][2] : village[road[i][1]][road[i][0]];
    }
    priority_queue<pair<int, int> > pq; // <-거리, 노드>
    // dijkstra algorithm
    for (int i = 1; i <= N; i++) {
        D[i] = village[1][i];
        pq.push(make_pair(-D[i], i));
    }
    
    while (!pq.empty()) {
        int cost = -pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();
        
        // if (D[currentNode] < cost) continue;
        
        // 인접 정점 모두 검사
        for (int i = 1; i <= N; i++) {
            if (D[currentNode] + village[currentNode][i] < D[i]) {
                D[i] = D[currentNode] + village[currentNode][i];
                pq.push(make_pair(-D[i], i));
            }
        }
    }
    
    for (int i = 1; i <= N; i++) {
        if (D[i] <= K) ++answer;
        // cout << D[i] << ", ";
    }
    return answer;
}