📒コンセプトの使用

📌問題の説明

📌インプリメンテーション

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

using namespace std;


int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    //Dijkstra사용을 위한 queue
    queue<int> current;
    //최소값을 저장하는 백터
    vector<int> dist(N+1, 100000);
    //마을의 경로와 가중치 저장.
    vector<vector<pair<int, int>>> route(N+1);
    
    current.push(1);
    dist[1]=0;
    
    for(int i=0; i<road.size(); i++){
        route[road[i][0]].push_back({road[i][1], road[i][2]});
        route[road[i][1]].push_back({road[i][0], road[i][2]});
    }
	
    //Dijkstra Algorithm사용
    while(!current.empty()){
        int cur=current.front();
        current.pop();
        for(int i=0; i<route[cur].size(); i++){
            if(dist[route[cur][i].first]==100000||dist[route[cur][i].first]>dist[cur]+route[cur][i].second){
                dist[route[cur][i].first]=dist[cur]+route[cur][i].second;
                current.push(route[cur][i].first);
            }
        }
    }
    
    for(int i=1; i<dist.size(); i++){
        if(dist[i]<=K){
            answer++;
        }
    }
    
    return answer;
}

📌注意点