[프로그래머스 lv 2 ] - 배달

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

코딩테스트 연습 - 배달

 

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

using namespace std;
vector<int> result; //1번부터 각각의 번호들까지의 가중치 저장 
vector < pair<int, int>> saveRoad[51]; //간선정보
void Dijkstra(int N)
{
	priority_queue<pair<int, int>> pQ;
	pQ.push(make_pair(1, 0)); //1번지점부터 시작 

	result.resize(N + 1, 2e9);

	result[1] = 0; //1번 자기자신 가중치는 0

	while (!pQ.empty())
	{
		int cur = pQ.top().first; //현재 번호
		int weight = pQ.top().second; //현재 가중치
		pQ.pop();

		if (result[cur] < weight) //저장되어있는 가중치가 더 낮으면 패스
			continue;

		for (int i = 0; i < saveRoad[cur].size(); i++) 
		{
			int nextNum = saveRoad[cur][i].first;
			int nextWeight = saveRoad[cur][i].second + weight;

			if (nextWeight < result[nextNum])
			{
				result[nextNum] = nextWeight; //1번부터 nextNum번까지의 가야하는 가중치 저장
				pQ.push(make_pair(nextNum, result[nextNum]));
			}
		}
	}
}
int solution(int N, vector<vector<int>> road, int K) {
	int answer = 0;

	for (int i = 0; i < road.size(); i++)
	{
		saveRoad[road[i][0]].push_back(make_pair(road[i][1], road[i][2]));//연결된 도로와 가중치 입력		
		saveRoad[road[i][1]].push_back(make_pair(road[i][0], road[i][2]));
	}
	Dijkstra(N);
	for (int i = 1; i <= N; i++)
	{
		if (result[i] <= K)
		{
			answer++;
		}
	}

	return answer;
}