최소비용 구하기 2 (feat. 백준, 11779번)

최소비용 구하기 2
https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> arr1[1001];
int arr2[1001], visit[1001];
vector<int> ans;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M, dx, dy;
	cin >> N >> M;
	for (register int i = 1; i <= N; ++i)
			arr2[i] = static_cast<int>(1e9);
	for (register int m = 0, x, y, c; m < M; ++m)
		cin >> x >> y >> c, arr1[x].push_back(make_pair(y, c));
	cin >> dx >> dy;

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push(make_pair(0, dx));
	arr2[dx] = 0;
	while (!q.empty()) {
		auto v = q.top(); q.pop();
		auto c1 = v.first, x = v.second;
		if (x == dy)
			break;
		if (arr2[x] < c1)
			continue;
		for (auto iter = arr1[x].begin(); iter != arr1[x].end(); ++iter) {
			auto y = iter->first, c2 = iter->second;
			if (arr2[y] > c1 + c2) {
				visit[y] = x;
				arr2[y] = c1 + c2;
				q.push(make_pair(arr2[y], y));
			}
		}
	}
	int t = dy;
	while (t) {
		ans.push_back(t);
		t = visit[t];
	}

	cout << arr2[dy] << "\n" << ans.size() << "\n";
	for (auto iter = ans.rbegin(); iter != ans.rend(); ++iter)
		cout << *iter << " ";
	return 0;
}
// *&)*@*

전형적인 다익스트라 알고리즘을 적용하는 문제입니다.

개념에 대해서만 알고 있다면 문제 풀이 자체는 어렵지 않습니다.

아래 위키 내용을 정독하시기 바랍니다.

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전