BOJ 11779 : 최소비용 구하기 2 [C++]

 

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

11779번: 최소비용 구하기 2

 

문제 요약

가중치 있는 유향 그래프가 주어지고 시작 정점과 도착 정점이 주어졌을 때, 시작 정점에서 도착 정점까지의 경로의 가중치 합의 최솟값을 구하고, 경로에 속한 정점들을 방문 순서대로 출력하는 문제이다.

 

접근

기본 다익스트라 알고리즘에서 경로 추적을 해야 한다.

다익스트라를 수행하면서 정점들이 지나온 경로들을 새로운 2차원 벡터 R에 저장하였다.
벡터 R[i]에 저장된 값이 i번 정점이 지나온 정점들의 번호를 담은 벡터가 된다.

만약 최소 비용의 갱신이 일어날 경우, 현재의 최소 경로가 담긴 벡터를 덮어쓰도록 했다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ii = pair<int, int>;

vector<vector<ii> > V(1001);
vector<vector<int> > R(1001);
int N, M, a, b, c, A, B;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	for (cin >> N >> M; M--;) {
		cin >> a >> b >> c;
		V[a].push_back({ b,c });
	}
	cin >> A >> B;
	priority_queue<ii, vector<ii>, greater<> > Q;
	Q.push({ 0,A });
	int d[1001]{};
	fill(d, d + 1001, -1);
	d[A] = 0;
	while (!Q.empty()) {
		int dist = Q.top().first;
		int node = Q.top().second;
		Q.pop();
		if (dist > d[node])	continue;
		for (ii next : V[node]) {
			if (d[next.first] == -1 || dist + next.second < d[next.first]) {
				d[next.first] = dist + next.second;
				R[next.first] = R[node];
				R[next.first].push_back(node);
				Q.push({ d[next.first], next.first });
			}
		}
	}
	cout << d[B] << '\n' << R[B].size() + 1 << '\n';
	for (int i : R[B])	cout << i << ' ';
	cout << B;
}