[백준] 1916 최소비용 구하기 - C++

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

---

양의 가중치를 가지는 그래프이니 다익스트라를 사용하면 된다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M;
const int INF = 1e9;
vector<pair<int, int> > graph[1001]; //{거리, 번호}
vector<int> dist;
void daik(int start) {
	dist.assign(N + 1, INF);
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > pq;
	dist[start] = 0;
	pq.push({0, start});
	while (!pq.empty()) {
		auto [cur_dist, cur] = pq.top();
		pq.pop();
		if (dist[cur] < cur_dist) {
			continue;
		}
		for (auto [next, cost] : graph[cur]) {
			if (dist[next] > cur_dist + cost) {
				dist[next] = cur_dist + cost;
				pq.push({dist[next], next});
			}
		}
	}
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].push_back({ v,w });
	}
	int s, e;
	cin >> s >> e;
	daik(s);
	cout << dist[e];
	return 0;
}

이전 글의 코드와 매우 매우 유사한 코드이다. main함수 조금 바뀐 거 말곤 모두 같다.

그러니 daik함수에 대한 설명은 이전 글을 참고하도록 하자.

2025.07.11 - [백준] - [백준] 1753 최단경로 - C++

[백준] 1753 최단경로 - C++

main함수에서의 변경점은, 결과를 출력할 때 모든 노드까지의 거리가 아니라

목표 노드까지의 거리만 출력하면 된다는 것이다.

---

다익스트라 좀 재밌는거같다..

---