문제

#include <vector>
#include <utility> // pair
#include <queue> // dijkstra
#include <algorithm> // min
#define MAX 51
#define INF 0x7FFFFFFF
using namespace std;

vector< pair<int, int> > graph[MAX]; // graph[from] =  { (to, weight), (to, weight), ... }
vector<int> dist(MAX, INF);

void update(int from, int old, priority_queue< pair<int, int> > * pq) {

	for (auto p : graph[from]) {
		int to = p.first;
		int weight = p.second;
		int newDist = old + weight; // 새로 계산된 거리

		// 더 짧은 경로를 발견하면 dist를 update하고 pq에 push
		if (newDist < dist[to]) {
			dist[to] = newDist;
			pq->push(make_pair(-newDist, to));
		}
	}
}

void dijkstra(int K) {
	dist[1] = 0;
	priority_queue< pair<int, int> > pq; // (weight, from)
	pq.push(make_pair(0, 1));

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

		if (dist[from] < weight) continue;
		else update(from, weight, &pq);
	}
}

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

	for (i = 0; i < MAX; i++) dist[i] = INF;

	for (auto v : road) {
		graph[v[0]].push_back(make_pair(v[1], v[2]));
		graph[v[1]].push_back(make_pair(v[0], v[2]));
	}

	dijkstra(K);

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