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

문제 풀이

 

약간만 생각하면 생각보다 쉽게 풀리는 문제다.

기존에 다익스트라를 통해서 한 정점에서 각 정점들의 최단 경로를 구했다면,

한 정점에서 시작해서 도착 정점까지의 경로들을 나열해야 한다.

 

어떻게 하면 나열할 수 있을까?

다익스트라의 원리를 보면 해결할 수 있다.

 

경로를 갱신할 때, 그때가 그 최단 경로이기 때문에 그 경로를 저장해주면 된다.

마치 'Union-Find'처럼 나의 부모가 누군지 저장해가면서, 최종적으로 역순으로 나열하면 그것이 최단 경로를 가지는 도시의 순서다.

 

출력할 때 약간 지저분할 수 있지만, 정리하면 다음과 같다.

1. 도착 지점까지의 최소 비용 = dist[도착 도시]

2. 도시의 개수 = 최단 경로를 가지는 도시의 순서의 도시를 카운트하면 된다.

3. 도시의 순서 = 도착 도시의 부모부터 시작해서 출발 도시까지 도시들을 담은 다음에 역순으로 출력하면 된다.

 

소스 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

const int INF = 987654321;
const int MAX = 1001;
int parent[MAX];
int dist[MAX];
int n, m, startCity, endCity;
vector<pair<int, int> > adj[MAX];

void dijkstra()
{
	fill(dist, dist + MAX, INF);
	for (int i = 1; i <= n; i++) parent[i] = -1;
	priority_queue<pair<int, int> > pq;
	pq.push({ 0, startCity });
	while (!pq.empty())
	{
		int cur = pq.top().second;
		int distance = -pq.top().first;
		pq.pop();

		if (dist[cur] < distance) continue;

		for (int i = 0; i < adj[cur].size(); i++)
		{
			int next = adj[cur][i].first;
			int nextDistance = adj[cur][i].second + distance;
			// 더 짧은 경로가 있다면 해당 경로로 갱신하는 타이밍,
			// 이때가 최단 경로이므로 부모를 저장한다. (추적하기 위해서)
			if (dist[next] > nextDistance)
			{
				dist[next] = nextDistance;
				parent[next] = cur;
				pq.push({ -nextDistance, next });
			}
		}
	}

	cout << dist[endCity] << '\n';
	int cnt = 0, cur = endCity;
	vector<int> v;
	v.push_back(cur);
	while (parent[cur] != startCity)
	{
		v.push_back(parent[cur]);
		cur = parent[cur];
	}
	v.push_back(startCity);
	reverse(v.begin(), v.end());

	cout << v.size() << '\n';
	for (auto i : v)
	{
		cout << i << ' ';
	}
	cout << '\n';
}

void input()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].emplace_back(b, c);
	}
	cin >> startCity >> endCity;
}

void solve()
{
	input();
	dijkstra();
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	solve();
	return 0;
}