[BOJ] 백준 9370번: 미확인 도착지

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

9370번: 미확인 도착지

 

시작점 s와 지나간 두 정점 g와 h의 정보, 전체 경로들에 대한 정보 및 목적지 후보 t가 주어질 때,

시작점에서 목적지까지 최단 경로가 시작점에서 g와 h를 잇는 간선을 지나 목적지까지 가는 최단경로의 비용이 같은 목적지 후보들을 찾는 문제입니다.

먼저 시작점에서 모든 정점까지 가는 최단 경로를 구합니다. 우선순위 큐를 사용한 다익스트라로 빠르게 구할 수 있습니다. (SPFA + SLF 도 가능)

	int dist[2001];
	fill(dist, dist + 2001, 2e9);
	dist[s] = 0;
	pq.push({ 0, s });
	while (!pq.empty()) {
		int node = pq.top().second;
		pq.pop();
		for (auto nxt : v[node]) {
			if (dist[nxt.first] > dist[node] + nxt.second) {
				dist[nxt.first] = dist[node] + nxt.second;
				pq.push({ -dist[nxt.first], nxt.first });
			}
		}
	}

그런 다음 두 정점 g와 h에서 시작하는 거리를 똑같이 구할 수 있습니다.

	int disth[2001];
	fill(disth, disth + 2001, 2e9);
	disth[h] = 0;
	pq.push({ 0, h });
	while (!pq.empty()) {
		int node = pq.top().second;
		pq.pop();
		for (auto nxt : v[node]) {
			if (disth[nxt.first] > disth[node] + nxt.second) {
				disth[nxt.first] = disth[node] + nxt.second;
				pq.push({ -disth[nxt.first], nxt.first });
			}
		}
	}

	int distg[2001];
	fill(distg, distg + 2001, 2e9);
	distg[g] = 0;
	pq.push({ 0, g });
	while (!pq.empty()) {
		int node = pq.top().second;
		pq.pop();
		for (auto nxt : v[node]) {
			if (distg[nxt.first] > distg[node] + nxt.second) {
				distg[nxt.first] = distg[node] + nxt.second;
				pq.push({ -distg[nxt.first], nxt.first });
			}
		}
	}

 

나눠서 구한 이유는

s에서 출발하여 g또는 h까지 가는데 최소 비용 dist[g] or dist[h]

g에서 h로 가는데 최소 비용 distg[h] 

h에서 g로 가는데 최소 비용 disth[g] 

g에서 목적지 후보까지 가는데 최소 비용 distg[i]

h에서 목적지 후보까지 가는데 최소 비용 disth[i] 

를 전부 구하면, 

dist[i] == min(dist[g] + distg[h] + disth[i], dist[h] + disth[g] + distg[i]) 인 목적지 후보들을 찾을 수 있습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>
#include <math.h>
#include <memory.h>
#include <set>
using namespace std;

void solve() {
	vector<pair<int,int> > v[2001];
	bool candi[2001] = { 0, };
	int n, m, t;
	cin >> n >> m >> t;
	int s, g, h;
	cin >> s >> g >> h;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}
	for (int i = 0; i < t; i++) {
		int num;
		cin >> num;
		candi[num] = 1;
	}

	priority_queue<pair<int, int>, vector<pair<int, int> > > pq;
	int dist[2001];
	fill(dist, dist + 2001, 2e9);
	dist[s] = 0;
	pq.push({ 0, s });
	while (!pq.empty()) {
		int node = pq.top().second;
		pq.pop();
		for (auto nxt : v[node]) {
			if (dist[nxt.first] > dist[node] + nxt.second) {
				dist[nxt.first] = dist[node] + nxt.second;
				pq.push({ -dist[nxt.first], nxt.first });
			}
		}
	}
	int disth[2001];
	fill(disth, disth + 2001, 2e9);
	disth[h] = 0;
	pq.push({ 0, h });
	while (!pq.empty()) {
		int node = pq.top().second;
		pq.pop();
		for (auto nxt : v[node]) {
			if (disth[nxt.first] > disth[node] + nxt.second) {
				disth[nxt.first] = disth[node] + nxt.second;
				pq.push({ -disth[nxt.first], nxt.first });
			}
		}
	}

	int distg[2001];
	fill(distg, distg + 2001, 2e9);
	distg[g] = 0;
	pq.push({ 0, g });
	while (!pq.empty()) {
		int node = pq.top().second;
		pq.pop();
		for (auto nxt : v[node]) {
			if (distg[nxt.first] > distg[node] + nxt.second) {
				distg[nxt.first] = distg[node] + nxt.second;
				pq.push({ -distg[nxt.first], nxt.first });
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (candi[i]) {
			if (dist[i] == min(disth[i] + dist[g] + distg[h], distg[i] + dist[h] + disth[g])) {
				cout << i << " ";
			}
		}
	}
	cout << "\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	for (; t--;) {
		solve();
	}
}