[BOJ] 백준 1238번: 파티

주어진 입력을 정방향, 역방향 2개의 벡터로 저장하여 파티가 열리는 노드를 시작으로 

다익스트라를 2번 수행하여 오고 가는데 걸린 최단 경로 합의 최대를 출력하는 문제

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
#include <math.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
vector<pii> v[10001];
vector<pii> v2[10001];
int dist[10001];
int dist2[10001];
int n, m, x;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m >> x;
	for (int i = 1; i <= n; i++) {
		dist[i] = 2e9;
		dist2[i] = 2e9;
	}
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[b].push_back({ a,c });
		v2[a].push_back({ b,c });
	}
	priority_queue<pii, vector<pii> > pq;
	pq.push({ 0,x });
	dist[x] = 0;
	while (!pq.empty()) {
		int node = pq.top().second;
		pq.pop();
		for (auto nxt : v[node]) {
			int cost = nxt.second;
			int next = nxt.first;
			if (dist[next] > dist[node] + cost) {
				dist[next] = dist[node] + cost;
				pq.push({ -dist[next],next });
			}
		}
	}
	pq.push({ 0,x });
	dist2[x] = 0;
	while (!pq.empty()) {
		int node = pq.top().second;
		pq.pop();
		for (auto nxt : v2[node]) {
			int cost = nxt.second;
			int next = nxt.first;
			if (dist2[next] > dist2[node] + cost) {
				dist2[next] = dist2[node] + cost;
				pq.push({ -dist2[next],next });
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dist[i] + dist2[i]);
	}
	cout << ans;
	
}