[BOJ] 9694번 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (C++)

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

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#define MAX 21
#define INF 987654321
using namespace std;

int d[MAX];
int pv[MAX];
vector<pair<int, int>> v[MAX];
stack<int> st;

void dijkstra(){
	d[0] = 0;
	
	priority_queue<pair<int, int>> pq;
	pq.push({0, 0});
	
	while(!pq.empty()){
		int cur = pq.top().second;
		int start_to_cur_dis = -pq.top().first;
		pq.pop();
		
		if(d[cur] < start_to_cur_dis) continue;
		
		for(int i = 0; i < v[cur].size(); i++){
			int next = v[cur][i].second;
			int start_to_next_dis = start_to_cur_dis + v[cur][i].first;
			
			if(start_to_next_dis < d[next]){
				d[next] = start_to_next_dis;
				pv[next] = cur;
				pq.push({-start_to_next_dis, next});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t;
	cin >> t;
	
	for(int k = 0; k < t; k++){
		int n, m;
		cin >> n >> m;
		
		for(int i = 0; i < MAX; i++){
			d[i] = INF;
			v[i].clear();
			pv[i] = -1;
		}
		
		for(int i = 0; i < n; i++){
			int a, b, c;
			cin >> a >> b >> c;
			v[a].push_back({c, b});
			v[b].push_back({c, a});
		}
		
		dijkstra();
		
		cout << "Case #" << k + 1 << ": ";
		if(d[m - 1] == INF) cout << -1;
		else{
			for(int i = m - 1; i > 0; )
				st.push(i = pv[i]);
			while(!st.empty()){
				cout << st.top() << " ";
				st.pop();
			}
			cout << m - 1;
		}
		cout << endl;
	}
	return 0;
}

 

다익스트라를 이용해 0부터 m-1까지 가는 데 드는 최소 비용을 기록하면서, 현재 정치인을 만나기 위해 누구를 먼저 만나야 하는지(Prev[])를 기록한다. m-1까지 가는 데 드는 최소 비용이 INF라면 만날 수 없다는 뜻이므로 -1을 출력하고, INF가 아니라면 스택을 이용해 경로를 역추적하여 출력한다.

 

경로를 역추적하는 방법을 학습할 수 있는 문제였다.