백준 11779 최소비용구하기2 c++ // 다익스트라 경로복원 방법

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

11779번: 최소비용 구하기 2

 

1. 다익스트라 경로복원 방법

1.1 pq에 push후 pre배열에 기록하면된다.

ex) pre[5]=3 // 5이전에 3임

pre[next.second] = cur.second;
				//경로복원 : (이전정점을 기록만하면된다)
				//pre[next.정점]=cur.정점

1.2 출력시 경로를 v 에 push

1.3 reverse(begin,end) 후 출력

	cout << d[en] << "\n";
	vector<int> v;
	int temp = en;
	while (temp != st) {
		v.push_back(temp);
		temp = pre[temp];
	}
	v.push_back(temp);
	cout << v.size() << "\n";
	reverse(v.begin(), v.end());

 

2. 전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, st, en;
vector<pair<int, int>> adj[20004];	//adj[1]:{2,3} 1->2로가는비용이 3임
int d[20004], pre[20004]; //시작~해당정점까지 최단거리
int INF = 987654321;

void re(int st, int en) {
	return re(st, pre[en]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	fill(d, d + 20004, INF);
	cin >> n >> m;
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ w,v });
	}
	cin >> st >> en;

	//{비용, 대상정점}
	priority_queue<pair<int, int>,
		vector<pair<int, int>>,
		greater<pair<int, int>>> pq;
	d[st] = 0;
	pq.push({ d[st],st });
	while (pq.size()) {
		auto cur = pq.top(); pq.pop();
		//2. 해당 거리가 최단거리테이블값과 다르면
		//더짧은경로가 있음 -> 무쓸모 -> pass
		if (d[cur.second] != cur.first) continue;
		//3. 이웃한 정점들에대해 직진보다 현재정점을 거치는게 더 싸면 
		//d갱신, 큐에추가
		for (auto next : adj[cur.second]) {
			if (d[next.second] > d[cur.second] + next.first) {
				d[next.second] = d[cur.second] + next.first;
				pq.push({ d[next.second] ,next.second });
				pre[next.second] = cur.second;
				//경로복원 : (이전정점을 기록만하면된다)
				//pre[next.정점]=cur.정점 
			}
		}
	}

	cout << d[en] << "\n";
	vector<int> v;
	int temp = en;
	while (temp != st) {
		v.push_back(temp);
		temp = pre[temp];
	}
	v.push_back(temp);
	cout << v.size() << "\n";
	reverse(v.begin(), v.end());
	for (auto i : v) cout << i << " ";
}