[백준] 1238 파티

[백준] 1238 파티

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

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_COST = 987654321;
const int MAX_V = 1000;

int V;
//<u, <v, w>>
vector <pair<int, int>> adj[MAX_V];
//<v, <u, w>>
vector <pair<int, int>> adj_reverse[MAX_V];

//파티 지점
int x;

//x에서 각 지점까지 최소 비용
//= 각각 학생들이 파티 -> 마을 이동 최소 시간 
vector<int> dist(MAX_V, MAX_COST);

//x에서 각 지점까지 reverse 최소 비용
//= 각각 학생들이 마을 -> 파티 이동 최소 시간
vector<int> dist_reverse(MAX_V, MAX_COST);

void priority_queue_dijkstra() {

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, x));
	dist[x] = 0;

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

		for (int i = 0; i < adj[curNode].size(); i++) {
			int nextNode = adj[curNode][i].first;
			int& nextW = adj[curNode][i].second;

			if (dist[nextNode] > curW + nextW) {
				dist[nextNode] = curW + nextW;
				pq.push({ -dist[nextNode], nextNode });
			}
		}
	}
}
void priority_queue_dijkstra_reverse() {

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, x));
	dist_reverse[x] = 0;

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

		for (int i = 0; i < adj_reverse[curNode].size(); i++) {
			int nextNode = adj_reverse[curNode][i].first;
			int& nextW = adj_reverse[curNode][i].second;

			if (dist_reverse[nextNode] > curW + nextW) {
				dist_reverse[nextNode] = curW + nextW;
				pq.push({ -dist_reverse[nextNode], nextNode });
			}
		}
	}
}


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

	//초기화
	for (int i = 0; i < MAX_V; ++i) {
		adj[i].clear(); 
		adj_reverse[i].clear();
		dist[i] = MAX_COST;
		dist_reverse[i] = MAX_COST;
	}

	int n, m; //정점 개수, 도로 개수
	cin >> n >> m >> x;
	x--;
	V = n;

	//도로 입력받기
	for (int i = 0; i < m; ++i) {
		int u, v, t;
		cin >> u >> v >> t;
		u--;
		v--;

		//u->v 단방향 도로
		//두 도시 사이 도로 최대 한 개
		adj[u].push_back({ v, t });
		//도로 역방향 정보 저장
		adj_reverse[v].push_back({ u, t });
	}

	priority_queue_dijkstra();
	priority_queue_dijkstra_reverse();

	int maxT = -1;
	for (int i = 0; i < n; ++i) {
		maxT = max(maxT, dist[i] + dist_reverse[i]);
	}
	cout << maxT;
	
	return 0;
}