[C++] 백준 5972번 - 택배 배송

간단한 다익스트라를 활용한 웰노운 문제

크게 어려운 문제는 아니었지만 다익스트라가 무향그래프일때 동시에 그래프를 업데이트 하는 것을 잊지 말자.

#include <bits/stdc++.h>
#define endl '\n'
#define INF 987654321
#define pii pair<int, int>
using namespace std;

int n, m;
vector<pii> v[50001];
int dist[50001];
priority_queue<pii, vector<pii>, greater<>> pq;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, w; cin >> a >> b >> w;
		v[a].push_back({ w, b });
		v[b].push_back({ w, a });
	}
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	}
	dist[1] = 0;
	pq.push({ dist[1], 1 });

	while (!pq.empty()) {
		int distance = pq.top().first;
		int curr = pq.top().second;
		pq.pop();

		if (dist[curr] < distance) continue;

		for (int i = 0; i < v[curr].size(); i++) {
			int next_dist = v[curr][i].first;
			int next = v[curr][i].second;
			if (distance + next_dist < dist[next]) {
				dist[next] = distance + next_dist;
				pq.push({ dist[next], next });
			}
		}
	}

	cout << dist[n] << endl;

	return 0;
}