백준 1238 - 파티 (feat. 역방향 다익스트라)

문제링크

• 백준 1238

문제설명

• N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
• 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
• 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
• 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

문제접근

• 역방향 다익스트라 를 이용하면 2번의 다익스트라로 해결할 수 있다.
  1. 목적지 -> 모든 정점
  2. (역방향) 목적지 -> 모든 정점 : 모든 정점에서 목적지로 가기 위한 최소 비용을 의미함
• 이 문제는 역방향 다익스트라를 적용하지 않고, N+1 번의 다익스트라를 통해서도 시간 내에 통과할 수는 있다. (문제 의도와는 다른 것으로 보이지만..)
  1. 목적지 -> 모든 정점
  2. N개의 출발점 -> 목적지

구현

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

#define MAX_N 10001

using namespace std;

int N, M, X;
vector<pair<int, int>> graph[MAX_N];
vector<pair<int, int>> reverseGraph[MAX_N];
vector<int> costFromParty(MAX_N, 0); // costFromParty[idx] -> X번 마을에서 idx번 마을까지 이동하는데 필요한 최소 비용
vector<int> costFromHouse(MAX_N, 0); // costFromHouse[idx] -> idx번 마을에서 X번 마을까지 이동하는데 필요한 최소 비용

void Dijkstra(int start, bool bForward)
{
	vector<int> dist(MAX_N, INT_MAX);
	dist[start] = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(0, start));

	while (!q.empty())
	{
		int u = q.front().second;
		int curCost = q.front().first;
		q.pop();

		if (dist[u] < curCost) continue;
		for (int i = 0; i < graph[u].size(); i++)
		{
			int v = graph[u][i].second;
			int x = graph[u][i].first;

			if (curCost + x < dist[v])
			{
				dist[v] = curCost + x;
				q.push(make_pair(curCost + x, v));
			}
		}
	}
	
	if (bForward) costFromParty = dist;
	else costFromHouse = dist;
}

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

	cin >> N >> M >> X;
	for (int i = 0; i < M; i++)
	{
		int from, to, cost;
		cin >> from >> to >> cost;
		graph[from].push_back(make_pair(cost, to));
		reverseGraph[to].push_back(make_pair(cost, from)); // 역방향 그래프
	}

	Dijkstra(X, true);
	int ans = 0;
	for (int i = 1; i <= N; i++)
	{
		graph[i].clear();
		for (int j = 0; j < reverseGraph[i].size(); j++)
		{
			graph[i].push_back(reverseGraph[i][j]);
		}
	}
	Dijkstra(X, false);
	for (int i = 1; i <= N; i++)
	{
		ans = max(ans, costFromHouse[i] + costFromParty[i]);
	}
	cout << ans << endl;
}