[백준 C++] 11779 최소비용 구하기 2 - 다익스트라

11779번: 최소비용 구하기 2

#include <iostream>
#include <climits>
#include <list>
#include <queue>
using namespace std;

typedef pair<int, int> p;
const int Infinite = INT_MAX;

int N, M;
list<p> Neighbor[1001];

int D[1001];
int P[1001];
deque<int> Way;

void Dijkstra(int Start, int End)
{
	for (int i = 1; i <= N; ++i)
	{
		D[i] = Infinite;
	}

	D[Start] = 0;
	P[Start] = Start;

	priority_queue<p, vector<p>, greater<p>> PQ;
	PQ.emplace(0, Start);
	while (!PQ.empty())
	{
		int Idx = PQ.top().second;
		int Cst = PQ.top().first;
		PQ.pop();

		if (Cst > D[Idx])
		{
			continue;
		}

		for (const p& N : Neighbor[Idx])
		{
			int NI = N.second;
			int NC = N.first;
			int NewCst = D[Idx] + NC;
			if (NewCst < D[NI])
			{
				D[NI] = NewCst;
				P[NI] = Idx;
				PQ.emplace(NewCst, NI);
			}
		}
	}
}

void MakeWay(int Start, int End)
{
	int Cur = End;
	Way.push_front(Cur);

	while (Cur != Start)
	{
		Cur = P[Cur];
		Way.push_front(Cur);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int A, B, W;
		cin >> A >> B >> W;
		Neighbor[A].emplace_back(W, B);
	}

	int S, E;
	cin >> S >> E;

	Dijkstra(S, E);
	MakeWay(S, E);

	cout << D[E] << '\n';
	cout << Way.size() << '\n';
	while (!Way.empty())
	{
		cout << Way.front() << ' ';
		Way.pop_front();
	}
}

---

 

전임자를 저장하는 다익스트라 문제입니다.

일반적인 다익스트라 알고리즘을 이용하되,

각 노드 까지의 최소 비용을 갱신할 때 전임자를 저장해주어야 합니다.

모든 최소 비용을 저장한 후에는 목적지 노드부터 출발지까지 전임자를 역추적합니다.

역추적할 때 거치는 모든 노드를 순서대로 저장해주면 그것이 바로 최소 비용 경로가 됩니다.