[C++] 백준 11779번: 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

다익스트라를 이용해 풀 수 있는 간단한 문제였다. 경로를 확인하기 위해 최단 거리를 업데이트 하면서 방문 직전 노드를 배열에 저장했다. 최단거리를 모두 구한 후, 목적지 노드에서부터 거꾸로 내려가며 스택에 저장하여 최단 경로를 얻을 수 있다.

런타임에러가 계속 발생했는데 원인을 찾느라 꽤 오랜 시간이 걸렸다. 변수 명을 안쪽 스코프에서 바깥의 것을 중복하기도 했고 무엇보다 가장 결정적인 것은 인접리스트를 이용하면서 인접리스트의 크기를 n이 아닌 m으로 지정했다는 것이다. 글자 하나 잘못 쓴 것 때문에 몇 시간을 허비했다. 

다익스트라 알고리즘은 타 블로그 강의 글 보면서 참고하지 않으면 작성을 잘 못 했었는데, 계속 사용하다보니 이제는 참고할 것 없어도 작성할 수 있을 만큼 된 것 같다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>
#define VP vector<pair<int, int>>
#define VVP vector<VP>

/* declare variables here */
int n, m;
VVP bus;
VI before;
stack<int> course;

/* define debug functions here */


/* define functions here */
long long dijkstra(int start, int dest) {
	vector<long long> dist(n, INF);
	dist[start] = 0;
	priority_queue<pair<int, long long>, vector<pair<int, long long>>, greater<pair<int, long long>>> pq;
	pq.push(make_pair(start, 0));
	while (!pq.empty()) {
		auto [here, cost] = pq.top();
		pq.pop();
		if (dist[here] < cost)
			continue;
		for (const auto& route : bus[here]) {
			const auto& [nextStop, nextCost] = route;
			if (cost + nextCost < dist[nextStop]) {
				dist[nextStop] = cost + nextCost;
				pq.push(make_pair(nextStop, dist[nextStop]));
				before[nextStop] = here;
			}
		}
	}
	return dist[dest];
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	/* Write input codes here  */
	cin >> n >> m;
	bus = VVP(n);
	FOR(i, m) {
		int from, to, cost;
		cin >> from >> to >> cost;
		bus[from - 1].push_back(make_pair(to - 1, cost));
	}
	int start, dest;
	cin >> start >> dest;

	/* Write solution codes here */
	before = VI(n, -1);
	long long ans = dijkstra(--start, --dest);
	int here = dest;
	course.push(dest + 1);
	while (before[here] != -1) {
		course.push(before[here] + 1);
		here = before[here];
	}
	cout << ans << EL;
	cout << course.size() << EL;
	while (!course.empty()) {
		cout << course.top() << ' ';
		course.pop();
	}
	cout << EL;

	return 0;
}