BOJ 백준 1238 파티 <다익스트라>

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

< 파티 >

 N개의 마을에 각각 학생들이 한 명씩 있고 특정 마을에서 파티가 열린다고 했을 때, 파티장에 갔다가 다시 집으로 돌아오는 시간이 가장 긴

경우를 찾는 문제이다. 음의 가중치가 존재하지 않기 때문에 다익스트라를 이용하여 풀면 되는 문제이다. 먼저 파티가 열리는 마을을 제외하므로

N-1개의 마을에서 파티장까지의 최단 경로를 모두 구해준 뒤에 파티장으로부터 각각의 마을까지의 최단경로를 구해주면 되는, 

다익스트라를 두 번 활용하면 되는 문제이다.

즉, 정리하자면 아래의 두 가지의 경로를 더해주면 특정 마을에서 파티장을 갔다오는데 걸리는 총 시간이 된다.,

1. N - 1개의 마을에서 파티장까지의 최단경로 구하기

2. 파티가 열리는 마을로부터 N - 1 개의 마을로의 최단경로 구하기

1번은 반복문을 통해 시작점을 파티가 열리는 마을을 제외하고 넣어주면 되고, 2번은 파티가 열리는 마을을 시작점으로 두면 된다.

이렇게 각 마을마다 경로들을 구해주고 그 중 최댓값을 찾아주면 된다.

#include <iostream>
#include <queue>
#include <vector>
#define SIZE 1001
#define INF 1000000000

using namespace std;

inline int Max(int a, int b) { return a > b ? a : b; }

void dijkstra_party(int total[], vector< pair<int, int> > map[], int n, int s, int to)
{
	priority_queue< pair<int, int> > pq;
	pq.push({ 0, s });

	int dist[SIZE];
	for (int i = 1; i <= n; ++i) dist[i] = INF;

	dist[s] = 0;
	
	while (!pq.empty())
	{
		int iTown = pq.top().second;
		int iCost = -pq.top().first;
		pq.pop();

		if (iCost > dist[iTown]) continue;

		for (int i=0; i<map[iTown].size(); ++i)
		{
			int next_town = map[iTown][i].first;
			int next_cost = iCost + map[iTown][i].second;

			if (dist[next_town] > next_cost)
			{
				dist[next_town] = next_cost;
				pq.push({-next_cost, next_town});
			}
		}
	}
	total[s] = dist[to];
}

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

	int n, m, x;
	vector< pair<int, int> > map[SIZE];

	int total[SIZE] = { 0 };

	cin >> n >> m >> x;

	map->resize(n + 1);
	for (int i = 0; i < m; ++i)
	{
		int from, to, time;
		cin >> from >> to >> time;

		map[from].push_back({ to, time });
	}

	// 파티장으로 가는 경로 구하기
	for (int i = 1; i <= n; ++i)
	{
		if (i == x) continue;
		dijkstra_party(total, map, n, i, x);
	}
        

// 파티장에서 집으로 돌아가는 경로 구하기
	priority_queue< pair< int, int> > pq;
	pq.push({ 0, x });

	int iDist[SIZE];
	for (int i = 1; i <= n; ++i) iDist[i] = INF;
	iDist[x] = 0;

	while (!pq.empty())
	{
		int cur = pq.top().second;
		int iCost = -pq.top().first;
		pq.pop();

		if (iCost > iDist[cur]) continue;

		for (int i = 0; i < map[cur].size(); ++i)
		{
			int next = map[cur][i].first;
			int next_cost = iCost + map[cur][i].second;

			if (iDist[next] > next_cost)
			{
				iDist[next] = next_cost;
				pq.push({ -next_cost, next });
			}
		}
	}
	int iMax = 0;

	for (int i = 1; i <= n; ++i)
	{
		iMax = Max(iMax, iDist[i] + total[i]);
	}

	cout << iMax << '\n';

	return 0;
}