백준 / 1238 파티 C++

www.acmicpc.net/problem/1238

1238번: 파티

다익스트라 알고리즘을 이용한 문제였습니다. 

단방향 그래프가 주어져 있을 때, 파티 지점까지 갈 때와 올 때 최소 경로로 올 때, 그 합이 최대인 것을 구하는 문제입니다.

 

다익스트라 알고리즘은 하나의 지점에서 모든 지점으로 가는 최단 경로를 찾을 때 유용하게 사용됩니다.

그래서 각 출발 지점에서 파티가 열리는 지점까지 모두 다익스트라로 돌리면 도착 지점은 항상 X로 정해져 있지만, 모든 지점에 대한 최단 경로를 찾기 때문에 조금 비효율적입니다.

N<=1000, M<=10000 이어서 작은 케이스이기 때문에 통과를 하긴 했지만, 케이스가 더 큰 경우면 파티 지점으로 갈 때는 다른 알고리즘을 사용하거나 문제를 조금 다르게 보면 됩니다.

 

다르게 보기 :

도착 지점은 항상 X이므로 역방향 그래프를 만들어서 X를 출발점으로 생각하고 각 지점에 대한 최단 경로를 구하면 그것이 원래 출발 지점에서 X로 가는 최단 경로와 일치

=> 그렇다면 정방향, 역방향 그래프 2번에 대해 다익스트라 알고리즘 2번 적용하면 해결 가능

 

 

코드는 다음과 같습니다. (역방향 그래프 구해서 다익스트라 2번 돌리는 것이 아닌 비효율적인 방법의 코드입니다.)

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

#define INF 987654321
int n, m, x;
int dist[1001]; // 출발점에서 도착점까지 최소 거리
vector<pair<int, int>>v[1001]; // {연결 지점, 거리}
int go[1001]; // 파티 장소까지 i번에서 출발해서 갈 때 최솟값
int back[1001]; // 파티장소에서 i번으로 올 때 최솟값
int result;

// 다익스트라로 출발 -> 도착 최소 거리 구하고
// 다시 다익스트라로 도착 -> 출발 최소거리 구해서
// 합이 최대인 것이 정답

void dist_init()
{
	fill(dist, dist + 1001, INF);
}

void init()
{
	cin >> n >> m >> x;
	for (int i = 0; i < m; i++) {
		int Start, End, Cost;
		cin >> Start >> End >> Cost;
		v[Start].push_back({ End,Cost });
	}
	result = 0;
	dist_init();
}

void dijkstra(int start, int last)
{
	dist_init();

	// 우선순위 큐 : {거리, 다음 지점}, 큐에는 거리 오름차순으로 (top이 거리 제일 짧음)
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
	pq.push({ 0,start });
	dist[start] = 0;

	while (!pq.empty())
	{
		int cost = pq.top().first; 
		int now = pq.top().second;
		pq.pop();

		for (int i = 0; i < v[now].size(); i++)
		{
			int ncost = v[now][i].second;
			int next = v[now][i].first;

			if (dist[next] > dist[now] + ncost) {
				dist[next] = dist[now] + ncost;
				pq.push({ ncost,next });
			}
		}
	}

	// 파티 장소에서 각 집으로 가는 경우
	if (last == -1) {
		for (int i = 1; i <= n; i++) {
			back[i] = dist[i];
		}
	}

	// 파티 장소로 가는 경우
	else
		go[start] = dist[last];
}

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

	init();

	for (int start = 1; start <= n; start++) {
		dijkstra(start, x);
	}

	dijkstra(x, -1);

	for (int i = 1; i <= n; i++) {
		result = max(result, go[i] + back[i]);
	}

	cout << result;
}