코딩무식자 전공생

문제출처: 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';
}

결과

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

풀이

출발->거쳐서->도착 의 패턴이 보여서 플로이드와샬 알고리즘이 끌리는데, 정점의 최대 갯수가 최대 1000이므로, 시간초과가 날 수 있습니다.

(그런데 684ms정도로 통과가 되긴하더라구요...아무튼 비추)

그래서 다익스트라를 쓰려는데, 다익스트라는 한 노드에서 다른 모든 노드로 가는 최단거리, 즉 ONE to ALL 알고리즘인데, 어떻게 적용해야할까요?

일반적인 생각은, X(목적지)에서 각 노드로 뻗어가는 최단거리와, 각각의 모든 노드에서 출발하는 최단거리들을 구한다음, 그 두 최단거리집합중

x에서 i노드로 가는 최단거리+ i에서 x로 가는 최단거리 중 가장 큰값이 답이 되겠죠.

그런데, 모든노드에서 다익스트라를 수행하므로 최대 1000*O(ElogV)= 1000* 10000*10= 약 1억므로 fail이 뜰 수도있습니다.

제출 시 거의 0ms로 통과될 수 있는 방법이있습니다. 조금만 생각해보면 매우 당연하고 간단합니다.

u,v,w를 입력받을 떄, 정점 u에서 v로 가는 가중치w만 연결시켜줄 뿐만 아니라, 역으로 v에서 u로가는 w로 가는 간선의 정보도 저장을해주면됩니다.

(역방향도 저장을 해준다는게, 방향그래프를 무방향그래프처럼 보겠다는겁니다. 단, 차이는 다익스트라를 두번의 경우로 나누어 돌려야하므로, 하나의 간선정보의 배열이 아닌 2개의 배열에 저장해야합니다.)

아래 그림을 보시면 이해가 갈겁니다.

원래의 그래프

역방향 그래프

보이시나요? 결국 각각의 그래프에서 목적지( 2번노드)부터 다익스트라를 돌린다음 각 노드로 가는 최단거리들을  합한값중 가장 큰값이 정답입니다.

즉, 시작->X+ X->도착 하는 값중 가장 큰 값을 구하는 것이므로, 문제의 조건그대로를 코드로 옮긴것입니다. 나머지는 코드를 보면서 이해하셨으면좋겠습니다.

코드 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int INF = 100000;
//정방향,역방향의 간선정보담을 두개의 벡터선언
vector<pair<int, int>>a1[1001];
vector<pair<int, int>>a2[1001];
int d[1001];
//파티장소(x)에서의 정방향+역방향에서의 다익스트라값의 합 저장
int ans[1001];
int n, m, x, u, v, w;
void dijkstra(int start, vector<pair<int, int>>arr[1001]);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m >> x;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v >> w;
		//x에서 정방향 다익스트라
		a1[u].push_back({ v,w });
		//x에서 역방향 다익스트라
		a2[v].push_back({ u,w });
		//결국 그림을그려보면, a1,a2에서의 x노드의 다익스트라 최단거리값의 합 중 가장큰값이 정답 
	}
	dijkstra(x, a1);
	dijkstra(x, a2);
	int max = 0;
	//저장된 값중에 가장 큰값이 정답(최단거리)
	for (int i = 1; i <= n; i++)
	{
		if (max < ans[i])
			max = ans[i];
	}
	cout << max << '\n';
}
void dijkstra(int start, vector<pair<int, int>>arr[1001])
{
	//각 최단거리를 INF로 초기화
	for (int i = 1; i <= n; i++)
		d[i] = INF;
	d[start] = 0;
	priority_queue<pair<int, int>>pq;
	pq.push({ 0,start });
	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 < arr[current].size(); i++)
		{
			int next = arr[current][i].first;
			int next_distance = arr[current][i].second + distance;
			if (d[next] > next_distance)
			{
				d[next] = next_distance;
				pq.push(make_pair(-next_distance, next));
			}
		}
	}
	//더해서 저장시킴 (정방향+역방향 총 2번 삽입하여 더해진값저장)
	for (int i = 1; i <= n; i++)
		ans[i] += d[i];
}

결과