백준 1238(파티)

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

1238번: 파티

 

모든 N개의 집에서 X까지 왕복하는 거리 중 최대 거리를 구하는 방법

 

1->X + X->1 

2->X + X->2

.

..

 

N->X + X->N

 

최단거리를 구하는 알고리즘이 필요하다는 걸 알 수 있다. 

 

X에서 나머지집까지의 거리를 구하는 알고리즘이 쉽게 있다.

 

한 지점에서 모든 다른 지점까지의 최단거리를 구하는 다익스트라 

 

그러면 이제 나머지 N개에서 X까지의 거리를 구하는 알고리즘이 필요하다 

 

이건 다익스트라에 대한 이해도를 물어보는 문제인것같다.

 

나머지 N개에서 X까지 거리를 구하는 알고리즘도 다익스트라 알고리즘이다. 

언어에서 바라볼 것이 아니라 수학적으로 1->다수로 봐야한다. 

 

그래서 그냥 X에서 N개까지 최단거리를 두 번 구하면 된다. 

물론 양방향이므로 한번은 가는쪽 한번은 오는쪽으로 구하면 된다.

 

		if (check) {
			for (int i = 1; i <= N; i++) {
				if (dist[i][check] > dist[p.second][check] + road[p.second][i]) {
					dist[i][check] = dist[p.second][check] + road[p.second][i];
					pq.push(make_pair(-dist[i][check], i));
				}
			}
		}
		else {
			for (int i = 1; i <= N; i++) {
				if (dist[i][check] > dist[p.second][check] + road[i][p.second]) {
					dist[i][check] = dist[p.second][check] + road[i][p.second];
					pq.push(make_pair(-dist[i][check], i));
				}
			}

		}

 

다익스트라 함수 내에서

bool check를 사용해서 두 번 처리했다.

 

	for (int i = 1; i <= N; i++) {
		if (X == i) continue;
		pq.push(make_pair(-road[X][i], i));
	}
	dij(true);
	while (!pq.empty()) {
		pq.pop();
	}
	for (int i = 1; i <= N; i++) {
		if (X == i) continue;
		pq.push(make_pair(-road[i][X], i));
	}
	dij(false);

 

값들을 집어 넣을때도 양방향으로 한 번씩 집어넣었다.

 

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
#define MAX 1001

priority_queue<pair<int, int> > pq;
pair<int, int> p;
int dist[MAX][2];
int road[MAX][MAX];
int N, M, X, a, b, c, max_n = -1;
bool checked[MAX][2] = { false };


void dij(bool check) {
	while (!pq.empty()) {
		p = pq.top();
		pq.pop();
		if (checked[p.second][check]) continue;
		checked[p.second][check] = true;
		if (check) {
			for (int i = 1; i <= N; i++) {
				if (dist[i][check] > dist[p.second][check] + road[p.second][i]) {
					dist[i][check] = dist[p.second][check] + road[p.second][i];
					pq.push(make_pair(-dist[i][check], i));
				}
			}
		}
		else {
			for (int i = 1; i <= N; i++) {
				if (dist[i][check] > dist[p.second][check] + road[i][p.second]) {
					dist[i][check] = dist[p.second][check] + road[i][p.second];
					pq.push(make_pair(-dist[i][check], i));
				}
			}

		}
	}
}

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

	cin >> N >> M >> X;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		road[a][b] = c;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			if (road[i][j] == 0) {
				road[i][j] = 987654321;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if (X == i) continue;
		dist[i][1] = road[X][i];
		dist[i][0] = road[i][X];
	}


	for (int i = 1; i <= N; i++) {
		if (X == i) continue;
		pq.push(make_pair(-road[X][i], i));
	}
	dij(true);
	while (!pq.empty()) {
		pq.pop();
	}
	for (int i = 1; i <= N; i++) {
		if (X == i) continue;
		pq.push(make_pair(-road[i][X], i));
	}
	dij(false);

	for (int i = 1; i <= N; i++) {
		if (max_n < dist[i][0] + dist[i][1]) max_n = dist[i][0] + dist[i][1];
	}

	cout << max_n << "\n";

}