[c++/백준] 1916번: 최소비용 구하기

문제 링크

1916번: 최소비용 구하기

풀이

우선순위 큐를 이용한 다익스트라 문제

1. M개의 입력값은 arr 벡터의 start 인덱스에 pair<end, distance>를 넣는다.
2. dp는 출발 도시에서 인덱스 i 도시까지의 최소 거리가 되는 벡터가 될텐데, 아직 갱신이 안 된 상태니까 무한대 값을, 출발 도시 인덱스에는 0을 넣어준다.
3. 우선순위 큐를 이용하는 이유는, 최소 거리의 도시부터 가기 위해 사용하고, pq에 pair<0, 출발 도시>를 넣고 pq가 빌 때까지 반복한다.
   3-1. dist에는 pq.top().first의 음수값을 넣어준다. (우선순위 큐는 기본 내림차순이기 때문에, 우리는 오름차순으로 구해야 함)
   3-2. dp[here]보다 dist가 크다면 갱신할 필요가 없기 때문에 continue
   3-3. 이제 here과 연결된 도시(next)의 거리를 갱신해야 하는데, dp[next]가 dp[here]+nextDist보다 크다면, 더 작은 거리로 갱신된다.
   3-4. next와 연결된 도시와의 갱신을 위해 pq에 pair<-nextDist, next>를 넣는다.

코드

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

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	vector<vector<pair<int, int>>> arr(n+1);
	vector<int> dp;

	for (int i = 0;i < m;i++) {
		int s, e, cost;
		cin >> s >> e >> cost;
		arr[s].push_back(make_pair(e, cost));
	}
	int stt, end;
	cin >> stt >> end;

	dp.resize(n + 1, 1000000000);
	
	dp[stt] = 0;

	priority_queue<pair<int,int>> pq;
	pq.push(make_pair(0, stt));

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

		if (dp[here] < dist) continue;
		
		for (int i = 0;i < arr[here].size();i++) {
			int next = arr[here][i].first;
			int nextDist = arr[here][i].second;
			if (dp[next] > dp[here] + nextDist) {
				dp[next] = dp[here] + nextDist;
				pq.push(make_pair(-nextDist, next));
			}
		}
	}

	cout << dp[end];
	
	return 0;
}