백준 1916번 최소 비용 구하기

문제링크

문제 해설

대표적인 다익스트라 알고리즘의 유형이다. 가중치 그래프이며, 특정 도시간 최소비용을 구하는 문제이기 때문이다.

따라서 우선순위 큐를 이용하여 접근하였다.

1. 그래프 설정
출발, 도착 도시가 있으며 도시간 비용을 입력으로 준다.
비용은 100,000보다 작기에 초기 값은 이보다 큰 값을 설정해준다. 임의로 987654321로 설정한다.
또한 출발 도시로부터 각 도시까지의 비용을 저장할 배열 dist를 만든다.
거리도 최소비용만을 저장할 것이기에 987654321로 설정한다.

2. 입력
도시간 비용이 여러 개가 된다하더라도 중요한 것은 최소비용이다.
그러므로 그래프에는 그 중 최소값만을 저장한다.

3. 비용 계산
우선순위 큐에 (비용, 도시)를 넣는다. 처음에는 출발 도시를 push한다.
그리고 큐로부터 하나씩 꺼낸다. 이 떄의 도시를 from이라 하자.
from으로부터 연결된 도시를 하나씩 살펴본다. 연결된 도시를 to라고 한다.
만약 dist[to]가 (dist[from] + from-to간의 비용)보다 크다면 최소 비용은 후자가 되는 것이다.
따라서 dist[to]를 (dist[from] + from-to간의 비용)로 수정한다. 그리고 큐에 (비용, to)를 넣어준다.
큐에 넣어주는 이유는 to까지의 비용이 갱신되었기 때문에 to와 연결된 다른 도시의 비용도 갱신될 수 있기 때문이다.
위와 같이 우선순위 큐가 빌 때까지 확인한다.
따라서 dist[도착도시]는 출발-도착 도시의 최소 비용을 뜻한다.

소스코드

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

// 백준 1916번 최소비용-구하기

using namespace std;

// 1. 도시간 최소비용 => 다익스트라.
// 2. 우선순위 큐 이용.
typedef pair<int, int> pi;
int map[1001][1001];
int dist[1001];
int INF = 987654321;
int n, m;

// 1.
int dji(int start, int end) {
	priority_queue<pi,vector<pi>,greater<pi>> pq;

	pq.push({ 0,start });
	dist[start] = 0;

	while (!pq.empty()) {
		int cost = pq.top().first;
		int from = pq.top().second;
		pq.pop();
		for (int i = 1; i <= n; i++) {
			if (map[from][i] !=INF) {
				if (dist[i] > dist[from] + map[from][i]) {
					dist[i] = dist[from] + map[from][i];
					pq.push({ dist[i],i });
				}
			}
		}
	}
	return dist[end];
}

int main() {
	cin >> n;
	cin >> m;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			map[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		map[start][end] = min(map[start][end], cost);
	}

	int start, end;
	cin >> start >> end;
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	}
	
	cout << dji(start, end) << endl;

	return 0;
}