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

문제 링크: https://www.acmicpc.net/problem/11779

 

다익스트라 알고리즘으로 최단경로를 찾고, 역추적해 최단경로를 출력하는 문제입니다.

다익스트라 알고리즘에 parent 배열만 추가해주면 됩니다

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;


const int INF = 987654321;

vector<pair<int, int>> adj[1000];	// idx, cost
vector<int> parent;
vector<int> dist;

int n, m;

int dijkstra(int src, int dst) {
	parent = vector<int>(n, -1);
	dist = vector<int>(n, INF);
	priority_queue<pair<int, int>> pq;	// cost(-), idx
	pq.emplace(0, src);
	dist[src] = 0;

	while (!pq.empty()) {
		auto [cost, idx] = pq.top();
		pq.pop();

		cost = -cost;

		if (dist[idx] < cost) continue;

		for (auto& edge : adj[idx]) {
			auto next = edge.first;
			auto nextDist = cost + edge.second;

			if (dist[next] > nextDist) {
				dist[next] = nextDist;
				pq.emplace(-nextDist, next);
				
				parent[next] = idx;
			}
		}
	}

	return dist[dst];
}

void print_path(int dst) {
	vector<int> path;

	while (dst != -1) {
		path.push_back(dst);
		dst = parent[dst];
	}

	cout << path.size() << '\n';
	for (auto it = path.rbegin(); it != path.rend(); ++it)
		cout << (*it)+1 << ' ';
	cout << '\n';
}

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

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		--a, --b;

		adj[a].emplace_back(b, c);
	}

	int s, d;
	cin >> s >> d;
	--s, --d;

	cout << dijkstra(s, d) << '\n';
	print_path(d);
	
	return 0;
}

최단경로가 여러개 존재하면 아무거나 출력해도 됩니다