BOJ 1238 파티

이 문제는 기본적으로 A - B까지 갈수 있는 경로 중 최단 시간을 구하는 다익스트라 응용 문제이다.

기존에 자주 출제되는 다익스트라는 무방향 그래프로  A - B 까지의 최단 경로와  B - A 까지의 최단 경로는 같다. 하지만 이 문제는 방향 그래프로 A - B 까지의 최단 경로와 B - A 까지의 최단 경로가 다르다. 따라서 문제에서 학생들이 오고 가는데 가장 오래 걸리는 학생의 소요시간을 구하기 위해서는 다익스트라를 두번 돌려주어야 한다.

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define INF 987654321
using namespace std;

int n, m, x;
vector<pair<int,int>> adj[1001];

int dajik(int start, int end)
{
	vector<int> dist(n + 1, INF);
	priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

	dist[start] = 0;
	pq.push({ 0,start });

	while(!pq.empty())
	{
		int cur_dist = pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		for(int i = 0; i < adj[cur_node].size(); i++)
		{
			int next_node = adj[cur_node][i].first;
			int next_dist = adj[cur_node][i].second;
			if(dist[next_node] > (cur_dist + next_dist))
			{
				dist[next_node] = cur_dist + next_dist;
				pq.push({ cur_dist + next_dist, next_node });
			}
		}
	}
	return dist[end];
}

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

	cin >> n >> m >> x;

	for(int i = 0; i < m; i++)
	{
		int s, e, t;

		cin >> s >> e >> t;

		adj[s].push_back({ e,t });
	}
	
	int maxLength = 0;
	for(int i = 1; i <= n; i++)
	{
		int goParty = dajik(i, x);
		int goHome = dajik(x, i);

		maxLength = max(maxLength, (goParty + goHome));
	}

	cout << maxLength;
}