[BOJ/C++] 5972 택배 배송

문제

https://www.acmicpc.net/problem/5972

풀이

다익스트라 알고리즘
weighted graph에서 최단 경로 찾을 때 사용

1. main 함수에서 DFS와 똑같이 인접리스트 생성
2. dist 배열 INF로 초기화
3. 우선순위큐에 {0, 시작점} 삽입, dist[시작점] = 0 초기화
4. BFS 탐색하듯이 cost, cur 선언하고, 큐에서 pop()
5. 인접리스트 크기만큼 next랑 new_cost 선언하고 큐에 삽입하며 dist 배열 갱신해주기 !

⭐우선순위큐에서 최소힙 만들어주기 위해 cost를 음수값으로 넣어주기
⭐우선순위큐의 first는 cost, second는 node / 인접리스트의 first는 node, second는 cost 구별해주기

코드

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

using namespace std;

int n, m;
vector<pair<int, int>> v[50001];
int dist[50001];

void dijkstra(int start) {
	for (int i = 1; i <= n; i++) {
		dist[i] = 100000000001;
	}

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	dist[start] = 0;

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i].first;
			int new_cost = v[cur][i].second + cost;
			if (dist[next] > new_cost) {
				dist[next] = new_cost;
				pq.push({ -dist[next], next });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int ans = 100000000;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b, c });
		v[b].push_back({ a, c });
	}

	dijkstra(1);

	cout << dist[n];

	return 0;
}