백준 - 택배 배송 (5972) [C++]

 이 문제는 다익스트라 알고리즘을 사용하는 문제이다. 한 지점에서 한 지점의 최단 거리를 구하기 때문에 다익스트라를 사용하면 쉽게 풀 수 있다.

 

 주의할 점은 C++에서 우선순위 큐의 디폴트로 최대 힙이므로 cost를 -를 붙여서 넣어줘야 하고, pair<int, int> 를 우선순위 큐 내부에 사용할 경우 first부터 우선순위가 부여되므로 cost, next 순으로 넣어줘야 한다.

 

 

 

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

using namespace std;

#define INF 100000000

vector<pair<int, int>> edges[50001];
int dist[50001];

int dijkstra(int start, int end) {
	priority_queue<pair<int, int>> pq;

	dist[start] = 0;

	pq.push({ 0, 1 });

	while (!pq.empty()) {
		pair<int, int> temp = pq.top();
		int present = temp.second;
		int cost = -temp.first;
		pq.pop();

		if (cost > dist[present]) {
			continue;
		}

		for (int i = 0; i < edges[present].size(); i++) {
			int next = edges[present][i].first;
			int nextCost = edges[present][i].second + dist[present];

			if (nextCost < dist[next]) {
				dist[next] = nextCost;
				pq.push({ -nextCost, next });
			}
		}
	}

	return dist[end];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N, M;

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}

	for (int i = 0; i < M; i++) {
		int a, b, c;

		cin >> a >> b >> c;

		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}

	cout << dijkstra(1, N) << '\n';

	return 0;
}