백준 1238 파티 (C++)

1238: 파티

다익스트라 알고리즘을 이용하는 문제이다. 기존 다익스트라 문제와 다른 점은 각 정점의 왕복 최단 거리를 찾는 것이다. 왕복 거리를 구하기 위해 기존 다익스트라 알고리즘을 두번 사용하여 합을 구했다. 다익스트라 알고리즘을 알고 있으면 어렵지 않은 문제이다. 다만 다익스트라 알고리즘을 잘 활용할줄 알아야한다.

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

#define INF 987654321

using namespace std;

int N, M, X, res = 0;
vector<pair<int, int>> v[1001];
int d[1001];

int dijkstra(int start, int end) {
	priority_queue<pair<int, int>> pq;

	for (int i = 1; i <= N; i++) {
		d[i] = INF;
	}

	pq.push({ 0,start });

	while (!pq.empty()) {
		int distance = -pq.top().first;
		int current = pq.top().second;

		pq.pop();

		if (d[current] < distance) continue;

		for (int i = 0; i < v[current].size(); i++) {
			int next = v[current][i].first;
			int next_distance = distance + v[current][i].second;

			if (next_distance < d[next]) {
				d[next] = next_distance;
				pq.push({ -d[next],next });
			}
		}
	}

	return d[end];
}

void solution() {
	for (int i = 1; i <= N; i++) {
		if (i != X) {
			int tmp = dijkstra(i, X) + dijkstra(X, i);
			res = max(res, tmp);
		}
	}

	cout << res;
}

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

	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
	}

	solution();
	
	return 0;
}