BOJ (C/C++) 1238번: 파티

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

1238번: 파티

---

풀이

도착지에서 Dijkstra를 돌려 각자 집으로 돌아가는 거리를 먼저 계산 후, 각 출발지에서 도착지까지의 최단 거리를 구해 왕복 거리를 계산함.

---

코드

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector <pair<int, int>> V[1001];
int Distance[1001];
void Dijkstra(int start, int end, int N) {
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	int now, dis, next;
	int D[1001];

	fill(D, D + N, 10000000);
	D[start] = 0;
	pq.push({ 0,start });

	while (!pq.empty()) {
		now = pq.top().second, dis = pq.top().first;
		pq.pop();
		if (D[now] < dis) continue;

		for (int i = 0; i < V[now].size(); i++) {
			next = V[now][i].first, dis = V[now][i].second;
			if (D[next] > D[now] + dis) {
				D[next] = D[now] + dis;
				pq.push({ D[next],next });
			}
		}
	}
	if (start == end) {
		for (int i = 1; i <= N; i++) Distance[i] = D[i];
	}
	else Distance[start] += D[end];
}
int main() {
	int N, M, X;
	int s, e, w;
	int m = 0;
	scanf("%d %d %d", &N, &M, &X);
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &s, &e, &w);
		V[s].push_back({ e,w });
	}


	// 도착지에서 각자의 집으로 돌아가는 거리 구하기
	Dijkstra(X, X, N + 1);

	for (int i = 1; i <= N; i++) {
		if (i != X) Dijkstra(i, X, N + 1);
		if (m < Distance[i]) m = Distance[i]; // 최댓값 구하기
	}
	printf("%d", m);
	return 0;
}