백준 1916. 최소비용 구하기

최소비용 구하기

2차원 그래프 탐색, 다익스트라 문제

1. 간단 설명

---

전형적인 다익스트라 문제

출발점, 도착점, 비용이 주어지고

출발지에서 도착지까지 최소 비용을 구하는 문제

2. 예시

---

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

5개의 도시, 8개의 버스 노선

1에서 5까지 가는데 최소 비용은

1->3->5 로 4이다

3. 알고리즘

---

다익스트라 알고리즘

1. N, M 입력받기
2. 버스 노선 정보들 입력받기
3. 출발, 도착점 입력받기
4. 출발점을 기준으로 다익스트라 수행
5. 구한 최단거리 출력

4. 소스코드

---

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

using namespace std;

int N, M;
int S, D;
vector< vector<pair<int, int>> > graph;
vector<int> dist;

void dijkstra() {
	dist[S] = 0;
	priority_queue< pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	pq.push({ 0, S }); // 비용 최소힙 

	while (!pq.empty()) {
		int now = pq.top().second;
		int now_cost = pq.top().first;
		pq.pop();

		// 이미 처리된 노드면 스킵
		if (dist[now] < now_cost) continue;

		// 이 노드와 연결된 노드 탐색
		for (pair<int,int> next : graph[now]) {
			int next_node = next.second;
			int next_cost = next.first;

			if (now_cost+ next_cost < dist[next_node]) {
				dist[next_node] = now_cost + next_cost;
				pq.push({ dist[next_node], next_node });
			}
		}
	}
}

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

	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N >> M;
	graph.resize(N + 1);
	dist.resize(N + 1, 21e8);
	for (int i = 0; i < M; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;

		graph[start].push_back({ cost, end });
	}
	cin >> S >> D;

	dijkstra();

	cout << dist[D];

	return 0;
}

우선순위 큐에서 greater<pair<int, int>>를 통해 이용해 최소힙을 구현했다

이를 사용할 땐 꼭 첫번째 값을 기준으로 정렬되므로 이에 주의할 것!!

그리고 처리된 노드를 스킵하는 부분이 굉장히 중요한데

우선순위 큐의 그리디 특성에 의해 항상 비용이 가장 작은 경로를 먼저 처리하기 때문에

뒤의 경로가 더 짧은 경우는 없으므로, 더 이상 보지 않아도 된다

먼저 도달하는 경우가 가장 최단거리임!