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

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

 

다익스트라 알고리즘 안에 parent를 저장하는 배열을 추가해서 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;
vector<vector<pair<int, int>>> graph;

struct VertexCost {
	bool operator<(const VertexCost& other) const {
		return cost < other.cost;
	}
	bool operator>(const VertexCost& other) const {
		return cost > other.cost;
	}
	int vertex;
	int cost;
};

void Dijkstra(int start, int end) {

	vector<int> best(n + 1, INT_MAX);
	vector<int> parent(n + 1, -1);
	priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq;

	pq.push({ start,0 });
	best[start] = 0;
	parent[start] = start;

	while (!pq.empty()) {
		auto curr = pq.top();
		pq.pop();

		int vertex = curr.vertex;
		int cost = curr.cost;
		if (cost > best[vertex])
			continue;

		for (auto next : graph[vertex]) {
			int nextCost = cost + next.second;
			if (nextCost >= best[next.first])
				continue;

			best[next.first] = nextCost;
			pq.push({ next.first,nextCost });
			parent[next.first] = vertex;
		}
	}
	int curr = end;
	vector<int> ans;
	while (true) {
		ans.push_back(curr);
		if (curr == start) break;
		curr = parent[curr];
	}
	reverse(ans.begin(), ans.end());
	cout << best[end] << "\n";
	cout << ans.size() << "\n";
	for (auto a : ans) {
		cout << a << " ";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	graph = vector<vector<pair<int, int>>>(n + 1, vector<pair<int, int>>());
	for (int i = 0; i < m; i++) {
		int a, b, d;
		cin >> a >> b >> d;
		graph[a].push_back({ b,d });
	}
	int start, end;
	cin >> start >> end;
	Dijkstra(start, end);
};