[프로그래머스][C++] 배달

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

코딩테스트 연습 - 배달

 

[프로그래머스][C++] 배달

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

int dijkstra(int N, int K, vector<vector<int>> map) {
	int ret = 0;
	priority_queue<pair<int, int>> pq;
	vector<int> dist(N + 1, 0x7fffffff);

	pq.push({ 0,1 });
	dist[1] = 0;

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

		for (int i = 1; i <= N; i++) {
			if (map[t][i]) {
				if (dist[i] > d + map[t][i]) {
					dist[i] = d + map[t][i];
					pq.push({ -dist[i], i });
				}
			}
		}
	}

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

int solution(int N, vector<vector<int> > road, int K) {
	vector<vector<int>> map(N + 1, vector<int>(N + 1, 0));

	for (int i = 0; i < road.size(); i++) {
		int n1 = road[i][0], n2 = road[i][1], dis = road[i][2];
		if (map[n1][n2] == 0 || map[n1][n2] > dis) {
			map[n1][n2] = dis;
			map[n2][n1] = dis;
		}
	}

	return dijkstra(N, K, map);
}