백준 1916 - 최소비용 구하기

문제링크

• 백준 1916

문제설명

• N개의 도시와 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다.
• 각 버스의 출발 도시와 도착 도시, 비용이 주어진다.
• A 도시와 B 도시가 주어질 때 A -> B 도시까지 가는데 드는 최소 비용을 구하라.

문제접근

• 다익스트라 알고리즘
  • 출발점이 정해져 있고, 정점 간 음이 아닌 정수의 가중치가 주어질 때 출발점에서 모든 정점까지의 최소 비용을 계산하는 알고리즘
• vector<pair<int, int>> table 의 인접리스트를 만들어서 가중치를 포함한 그래프 정점 정보를 담는다.
• 우선수위 큐 자료구조를 활용하여 가중치를 기준으로 최소 힙을 만든다.
  • priority_queue 자료형은 최대 힙이 기본 형태이므로 정렬 인자를 지정해줘야 한다. (ex. greater<pair<int, int>>)
  • pair<int, int> 데이터 타입을 우선순위 큐에 적용하는 경우 first 인자가 정렬 기준이 된다.
• 다익스트라를 적용하기 전에 출발점을 제외한 모든 정점까지의 비용은 INF 로 초기화 된 상태여야 한다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int N, M;

vector<pair<int, int>> table[1001];

int dijkstra(int s, int target) {
	// min heap (first 기준)
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(make_pair(0, s));
	int dist[1001];
	for (int i = 1; i <= N; i++) {
		dist[i] = INT_MAX;
	}
	dist[s] = 0;// 출발지로 가는 비용은 0

	while (!pq.empty()) {
		int u = pq.top().second;
		int w = pq.top().first;
		pq.pop();

		if (dist[u] < w) continue;

		for (int i = 0; i < table[u].size(); i++) {
			int v = table[u][i].second;
			int x = table[u][i].first;
			if (dist[v] > w + x) {
				dist[v] = w + x;
				pq.push(make_pair(w + x, v));
			}
		}
	}
	return dist[target];
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d", &N, &M);

	int departure, arrival;
	int u, v, w;
	for (int i = 0; i < M; i++) {
		// u -> v 로 갈때 비용 w
		scanf("%d %d %d", &u, &v, &w);
		table[u].push_back(make_pair(w, v));
	}
	scanf("%d %d", &departure, &arrival);
	int ans = dijkstra(departure, arrival);
	printf("%d\n", ans);
	return 0;
}