[C/C++] 백준 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개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

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

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;
#define INF 2100000000 // 21억

int T;
int n, m, t, s, g, h, a, b, d, x;
int scent, crossroad1, crossroad2;
int result_1[50001], result_2[50001];
vector<int> ans;
vector<pair<int, int>> road[50001];

void dijkstra(int start, int* result)
{
	queue<int> q;
	for (int i = 1; i <= n; i++)
		result[i] = INF;

	result[start] = 0;
	q.push(start);

	while (!q.empty())
	{
		int node = q.front();
		int dist = result[node];
		q.pop();

		for (int i = 0; i < road[node].size(); i++)
		{
			int next_node = road[node][i].first;
			int next_dist = road[node][i].second;

			if (result[next_node] > dist + next_dist)
			{
				result[next_node] = dist + next_dist;
				q.push(next_node);
			}
		}
	}
}


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

	cin >> T;

	while (T--)
	{
		// 정답,다익스트라 결과값,교차로 거리정보들 모두 초기화
		ans.clear();
		memset(result_1, 0, sizeof(result_1));
		memset(result_2, 0, sizeof(result_2));
		for (int i = 0; i < 50001; i++)
			road[i].clear();

		cin >> n >> m >> t; // 교차로, 도로, 목적지 수
		cin >> s >> g >> h; // 출발지, 후각1, 후각2

		for (int i = 0; i < m; i++) // 교차로 사이 거리 입력
		{
			cin >> a >> b >> d;

			road[a].push_back({ b,d });
			road[b].push_back({ a,d });

			if ((a == g && b == h) || (a == h && b == g))
				scent = d; // 후각으로 탐지하여 알아낸 교차로 거리
		}
		
		// 출발점에서의 다익스트라
		dijkstra(s, result_1); 

		// 후각으로 탐지한 도로에서의 다익스트라 (더 먼쪽이 가는 길의 방향입니다.)
		if (result_1[g] > result_1[h]) // 출발점 기준으로 crossroad1:가까운 쪽, crossroad2는 먼쪽
		{
			crossroad1 = h;
			crossroad2 = g;
		}
		else
		{
			crossroad1 = g;
			crossroad2 = h;
		}
		dijkstra(crossroad2, result_2);

		for (int i = 0; i < t; i++) // 목적지 후보 검사
		{
			cin >> x;
			// 출발지 ~ 목적지까지의 최단거리 == 출발지 ~ crossroad1 ~ crossroad2 ~ 목적지까지의 최단거리
			if (result_1[x] == result_1[crossroad1] + scent + result_2[x])
				ans.push_back(x);
		}

		sort(ans.begin(), ans.end()); // 정답 오름차순 정렬

		for (int i = 0; i < ans.size(); i++)
			cout << ans[i] << " ";
		cout << '\n';
	}
	
}

 

풀이 방법

 

개가 후각으로 탐지한 도로를 듀오가 지나가려면 해당 목적지에 최단거리로 가는 길에 후각으로 탐지한 도로가 경로에 포함되어야 한다.

개가 후각으로 탐지한 도로의 시작 교차로를 crossroad1, 끝 교차로를 crossroad2라고 하고,
첫 번째 테스트 케이스를 시각화하면 아래와 같다.

시작점에서의 다익스트라를 통해 최단거리를 계산한 정보를 result_1 배열에 담고

두 crossroad중에서 시작점과 가까운 곳이 crossroad1이고 먼 쪽이 crossroad2이다. 

 

그리고 먼 쪽(crossroad2)에서 다익스트라를 통해 목적지 까지의 최단거리를 계산한 정보를 result_2 배열에 담는다. 

 

출발지 ~ 목적지 까지의 최단거리와 출발지 ~ crossroad1 ~ crossroad2 ~ 목적지 까지의 최단거리가 같을 시에 해당 목적지가 듀오가 가려는 목적지임을 알 수 있다.

 

 

두 번째 케이스도 시각화한다면 아래와 같다.

 

6번 목적지의 경우 2번에서의 최단거리 경로는 교차로 1, 3번이 포함된다. (4번의 경유해서 가는 경로가 더 멀기 때문)

그리고 5번 목적지의 경우는 2번에서의 최단거리 경로는 바로 이어져있는 5만큼의 거리만 이동하면 최단거리이다.
즉, 교차로 1, 3번을 지날 필요가 없으므로 5는 목적지에서 제외하면 된다.

 

 

www.acmicpc.net/problem/9370

9370번: 미확인 도착지