[백준 1719] 택배

문제출처: https://www.acmicpc.net/problem/1719

풀이

기존의 다익스트라함수에 경로를 추적할수있는 배열을 추가하여 연산해야합니다.

일단 각 노드에서 경로를 추적할 수 있게 정점의 갯수만한 1차원배열을 선언합니다.

그리고 다익스트라를 수행중에  최단거리를 수정하는 연산과정에서  경로를 추적할 수 있게  다음과같이 1줄만 작성해주면됩니다.

trace[next]=current의 의미는 current노드에서 next노드까지의 경로가 있음을 의미하고, 구체적으로는 

최단거리중 next노드 바로전의 경로가(거치는 길이)current노드임을 의미합니다.

예를들어, 2번노드에서 다익스트라를 돌려서 아래와 같이 구해진 최단경로를 봅시다.

이렇게 최단거리가 구성되는데, 문제에서 주어진 경로표를 보면 2번노드에서의 최단거리중 n번노드로 갈 때 가장 먼저 거치는 노드의번호와 같음을 알 수 있습니다.(당연한건데 그림을 그려야 보임)

최단 거리를 수정하는 if문 안에 경로추적배열을 선언하고, 출력할 때, 

1. 시작노드랑 x번노드랑 같을 때(본인이므로 "-" 출력)

2. trace[index]=x일때 (index노드전에 x노드가 붙어있으므로, index출력

3. trace[index]=x가 아닐때 (식이 성립할 때 까지 경로를 거슬러 올라가서 index출력)

이 3가지만 고려해서 코드작성하시면됩니다.

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int INF = 200000;
vector<pair<int, int>>a[201];
int d[201];
int trace[201];
int n, m, u, v, w;
void dijsktra(int x);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i <m; i++)
	{
		cin >> u >> v >> w;
		a[u].push_back({ v, w });
		a[v].push_back({ u, w });
	}
	for (int i = 1; i <= n; i++)
		dijsktra(i);
}
void dijsktra(int x)
{
	for (int i = 1; i <= n; i++)
		d[i] = INF;
	d[x] = 0;
	priority_queue<pair<int, int>>pq;
	pq.push({ 0,x });
	while (!pq.empty())
	{
		int current = pq.top().second;
		int distance = -pq.top().first;
		pq.pop();
		if (d[current] < distance)continue;
		for (int i = 0; i < a[current].size(); i++)
		{
			int next = a[current][i].first;
			int next_dis = distance + a[current][i].second;
			//최단거리를 갱신할 때 
			if (d[next] > next_dis)
			{
				//갱신된 거리의 경로를 담음
				trace[next] = current;
				d[next] = next_dis;
				pq.push(make_pair(-next_dis, next));
			}
		}
	}
	//1번노드에서 다익스트라 끝났을때, 1에서 출발하는 각 노드까지의 최단경로그림그려보면
	//trace[index]=dis일때, dis에서 index로 가는길이있음.
	//이 성질을 이용해서 트랙출력
	for (int i = 1; i <= n; i++) {
		if (i == x)
			cout << "- ";
		else if (trace[i] == x)
			cout << i<<" ";
		else
		{
			//x노드에서 가장 가까운 거치는 노드탐색
			//trace[index]=x일때가 x에서 index로 가는길이있으면서 x노드바로 전 노드가index노드일때이므로
			//위조건을 만족하는 index가 가장먼져 거치는 수,
			int index = i;
			while (1)
			{
				if (trace[index] == x)
				{
					cout << index<<" ";
					break;
				}
				//아닐 시에 최단거리의 경로를 거슬러 올라가본다.
				else
					index = trace[index];
			}
		}
	}
	cout << '\n';
}

결과