[백준 1238] 파티

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

결과