[백준 9370] 미확인 도착지

문제 링크 : 9370번: 미확인 도착지 (acmicpc.net)

9370번: 미확인 도착지

문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

• 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

---

다익스트라 문제이다.

시작 지점 s 부터 목표 지점 x 까지의 최단 경로가 시작 지점 s 부터 교차로를 지나서 목표지점 x 까지의 최단 경로와 동일한지를 알아봐야 한다. 

다음과 같이 두 가지 경우를 고려해볼 수 있다.

 

 

① 출발 지점 s 에서 g 지점 까지 이동 후, 교차로 g-h 를 이동하고, h 에서 x 지점 까지 이동한다.

 

 

② 출발 지점 s 에서 h 지점 까지 이동 후, 교차로 h-g 를 이동하고, g 에서 x 지점 까지 이동한다.

 

s 에서 시작하는 경우와 h 에서 시작하는 경우와 g 에서 시작하는 경우 총 3가지 경우를 나눌 수 있다.

• int Dist_S[2001] : 출발 지점 s 부터 모든 지점까지의 최단 경로
• int Dist_H[2001] : h 지점 부터 모든 지점까지의 최단 경로
• int Dist_G[2001] : g 지점 부터 모든 지점까지의 최단 경로 

 

이제 ①, ② 에 대한 조건을 만족하는 경우는 다음과 같은 식으로 정리할 수 있다.

if (Dist_S[x] == Dist_S[g] + intersect_distance + Dist_H[x] ||
	Dist_S[x] == Dist_S[h] + intersect_distance + Dist_G[x])

 

이때 intersect_distance 는 교차로의 거리를 의미한다.

Dist_H 배열 또는 Dist_G 배열을 구한 후, Dist_H 를 먼저 구했다면 Dist_H[g] 가 교차로의 거리이고 Dist_G 를 먼저 구했다면 Dist_G[h] 가 교차로의 거리가 된다.

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int n, m, t;
int s, g, h;

vector<pair<int, int>> v[2001];
int Dist_S[2001], Dist_G[2001], Dist_H[2001];

void input() {
	int a, b, d;
	cin >> n >> m >> t;
	cin >> s >> g >> h;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> d;
		v[a].push_back({ b,d });
		v[b].push_back({ a,d });
	}
}

void init() {
	for (int i = 0; i <= 2000; i++) {
		v[i].clear();
		Dist_S[i] = Dist_G[i] = Dist_H[i] = INF;
	}
}

void dijkstra(int start, int Dist[]) {
	priority_queue<pair<int, int>> PQ;
	PQ.push({ 0, start });
	Dist[start] = 0;
	while (!PQ.empty()) {
		int dist = -PQ.top().first, x = PQ.top().second;
		PQ.pop();
		if (dist > Dist[x]) continue;
		for (int i = 0; i < v[x].size(); i++) {
			int next = v[x][i].first, next_dist = dist + v[x][i].second;
			if (next_dist < Dist[next]) {
				Dist[next] = next_dist;
				PQ.push({ -next_dist, next });
			}
		}
	}
}

void solution() {
	int x, intersect_distance;
	vector<int> result;

	dijkstra(s, Dist_S);
	dijkstra(g, Dist_G);
	intersect_distance = Dist_G[h];
	dijkstra(h, Dist_H);

	while (t--) {
		cin >> x;
		if (Dist_S[x] == Dist_S[g] + intersect_distance + Dist_H[x] ||
			Dist_S[x] == Dist_S[h] + intersect_distance + Dist_G[x])
			result.push_back(x);
	}

	sort(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++) cout << result[i] << " ";
	cout << endl;
}

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

	int T;
	cin >> T;
	while (T--) {
		init();
		input();
		solution();
	}

	return 0;
}