[알고리즘] 백준 11779번: 최소비용 구하기 2 (C++)

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

11779번: 최소비용 구하기 2

이 문제 또한 다익스트라를 통해 최소 비용을 구하고, 다익스트라에서 경로 역추적을 하여 최소 비용을 발생시키는 노드들의 배열을 담아서 main에서 이 노드들을 while을 통해 result배열에 담아 출력해주면 되는 간단한 문제였다.

 

하지만, 주어진 예제와 내 답이 달라서 틀린 건가 싶었지만 직접 그림을 그려보니 내 답도 만족하는 경우라서 혹시나 하는 마음에 제출을 해보니 맞았었다.

 

예제)

4
3
1 3 5

내 답)

4
3
1 4 5

노드 {1, 3, 4, 5}를 그래프로 나타내 보면 1에서 5로 가는 최소 비용이 {1, 3, 5}나 {1, 4, 5} 둘 다 최소 비용이 4라서 내 답도 답이 될 수 있다.

 

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#define MAX 1000 + 1
#define INF 987654321
#define pii pair<int, int>
using namespace std;

vector<pii> graph[MAX];
int trace[MAX];
int n, m;

struct cmp {
	bool operator()(pii& a, pii& b) {
		return a.second > b.second;
	}
};

int dijkstra(int node, int end) {
	priority_queue<pii, vector<pii>, cmp> pq;
	vector<int> dist(n + 1, INF);
	dist[node] = 0;
	pq.push({ node, 0 });
	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;

		pq.pop();

		if (dist[now] < cost) {
			continue;
		}

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push({ next, dist[next] });

				trace[next] = now;
			}
		}
	}

	return dist[end];
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({ b, c });
	}

	int s, d;
	cin >> s >> d;
	int firstAnswer = dijkstra(s, d);

	vector<int> result;
	result.push_back(d);

	int node = d;
	while (1) {
		if (trace[node] == s) {
			result.push_back(s);
			break;
		}
		else {
			node = trace[node];
			result.push_back(node);
		}
	}

	cout << firstAnswer << '\n';
	cout << result.size() << '\n';
	while (!result.empty()) {
		cout << result.back() << ' ';
		result.pop_back();
	}
	return 0;
}