백준 1238번 - 파티 (C++)

https://www.acmicpc.net/problem/1238

1238번: 파티

 

이 문제는 "맞았습니다" 를 받는 것 자체는 다익스트라 알고리즘을 알고있으면 어렵지 않은 문제이다. 

왜냐하면 문제 조건이 그렇게 까다롭지 않다. 

1, 2, 3, 4 중 X = 2 라면 1~4까지 모두 다익스트라 알고리즘으로 2까지의 최단거리를 저장하고, 2에서 다른 곳으로 가는 방법들을 다익스트라로 저장하면 된다. 

 

그러므로 노드가 4개이면, X 지점에서 다익스트라 한 번 , 그리고 N - 1번 다익스트라를 해야하므로 총 N번의 다익스트라 알고리즘이 필요하며 시간복잡도는

 

N^2LogN이 될 것이다. 그리고 N = 1000이기 때문에 약 3백만 정도의 연산이 필요하므로 TLE는 발생하지 않는다. 

 

그러나, 만약 노드의 수가 1000이 아니라 10000이었다면 이 문제는 TLE가 발생할수도 있다. 그래서 한 가지 더 발상이 필요하다. 

 

여기서 필요한 정보는 1,3,4 노드가 2번까지 얼마나 걸리는지가 알고싶은 것이다. 그래서 각자 다익스트라가 필요하다. 

그런데 만약 반전된 그래프에서 2에서 다익스트라를 한다면 ?

 

1,3,4에서 2까지의 최소거리를 구하는 것과 같은 효과를 얻을 수 있다!!

 

그래서 이 문제의 핵심은 각자 다익스트라를 하는 것이 아니라 주어진 그래프에서 1번, 반전된 그래프에서 1번의 다익스트라를 X 지점에서 하는 것이 정해이다. 이렇게하면 총 2번의 다익스트라 알고리즘이 필요하며, 무려 2NlogN으로 끝낼 수 있다. 

 

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

vector<pair<int, int>> graph_origin[1001];
vector<pair<int, int>> graph_reverse[1001];

int dist_origin[1001];
int dist_reverse[1001];

void dijk_origin(int x) {
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, x });
	dist_origin[x] = 0;

	while (!pq.empty()) {
		int now_node = pq.top().second;
		pq.pop();

		for (int i = 0; i < graph_origin[now_node].size(); i++) {
			int next_node = graph_origin[now_node][i].first;
			int next_value = graph_origin[now_node][i].second;

			if (dist_origin[next_node] > dist_origin[now_node] + next_value) {
				dist_origin[next_node] = dist_origin[now_node] + next_value;
				pq.push({ -next_value, next_node });
			}
		}
	}
}

void dijk_reverse(int x) {
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, x });
	dist_reverse[x] = 0;

	while (!pq.empty()) {
		int now_node = pq.top().second;
		pq.pop();

		for (int i = 0; i < graph_reverse[now_node].size(); i++) {
			int next_node = graph_reverse[now_node][i].first;
			int next_value = graph_reverse[now_node][i].second;

			if (dist_reverse[next_node] > dist_reverse[now_node] + next_value) {
				dist_reverse[next_node] = dist_reverse[now_node] + next_value;
				pq.push({ -next_value, next_node });
			}
		}
	}
}

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

	int N, M, X;
	cin >> N >> M >> X;

	for (int i = 0; i <= N; i++) {
		dist_origin[i] = 123141242;
		dist_reverse[i] = 123131241;
	}

	for (int i = 0; i < M; i++) {
		int s, e, cost;
		cin >> s >> e >> cost;
		graph_origin[s].push_back({ e, cost });
		graph_reverse[e].push_back({ s,cost });
	}

	dijk_origin(X);
	dijk_reverse(X);
	int answer = 0;
	for (int i = 1; i <= N; i++) {
		if (i == X) continue;
		answer = max(answer, dist_origin[i] + dist_reverse[i]);
	}

	cout << answer << '\n';
}

 

 

일반적인 방법시 220ms

반전된 그래프 방법시 0ms