[백준OJ] 11779번 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

---

 

 

풀이

1916번 최소비용구하기의 코드에 몇가지만 추가를 해주면 된다.

https://khu98.tistory.com/237

[백준OJ] 1916번 최소비용 구하기

 

다익스트라를 실행시키면서 최소비용이 갱신되는 노드가 있다면, 추적을 도와주는 trace배열에 자신 이전의 노드를 추가를 해준다. 다익스트라를 모두 실행시킨뒤, 도착지점부터 시작지점까지 trace를 이용하여 역추적을 한뒤, 그 결과를 reverse함수를 이용해서 거꾸로 출력시켜주면된다.

 

코드

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#define MAX	987654321
using namespace std;

vector<pair<int,int>> maze[1001];
int cost[1001];
int trace[1001];
bool visited[1001] = { 0 };
int n, m,st,en;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cost[i] = MAX;
	}
	for (int i = 0; i < m; i++) {
		int to, from, cost;
		cin >> to >> from >> cost;
		maze[to].push_back({ from,cost });
	}

	cin >> st >> en;
	priority_queue<pair<int,int>> pq;
	cost[st] = 0;
	trace[st] = -1;
	pq.push({ 0,st });

	while (!pq.empty()) {
		int now = pq.top().second;
		int dist = -pq.top().first;
		pq.pop();

		if (cost[now] < dist) continue;

		for (auto next : maze[now]) {
			int next_node = next.first;
			int next_cost = next.second;

			if (cost[next_node] > next_cost + dist) {
				cost[next_node] = next_cost + dist;
				trace[next_node] = now;
				pq.push({ -(next_cost + dist),next_node });
			}
		}
	}

	vector<int> result;
	result.push_back(en);
	int now_node = en;
	while (trace[now_node] != -1) {
		result.push_back(trace[now_node]);
		now_node = trace[now_node];
	}

	reverse(result.begin(), result.end());

	cout << cost[en] << "\n" << result.size() << "\n";
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << " ";
	}

	return 0;
}