[BOJ/백준 9370/C++] 미확인 도착지

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

9370번: 미확인 도착지

 

[문제 요약]

- 우리가 알아낸 것은 그들이 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개로 향하는 최단 경로의 일부이다.

- 시간 제한 : 3초

- 메모리 제한 : 256MB

 

[문제 풀이]

이번 문제는 다익스트라를 이용하여 목적지 후보 중 진짜 목적지들을 찾는 것이 핵심인 문제다.

 

일단 우리가 문제에서 얻을 수 있는 정보는 입력의 두 번째 줄에 들어오는 g와 h를 잇는 도로를 무조건 지난다는 것이 핵심이다.

 

g와 h를 잇는 도로를 X라고 했을 때 X를 무조건 지나는 경우는 다음과 같을 것이다.

• s에서 출발하여 X라는 도로를 g에서 진입하여 지나는 경우
• s에서 출발하여 X라는 도로를 h에서 진입하여 지나는 경우

이렇게 2가지의 경우를 생각해야 된다.

 

2가지 경우에서 어떤 경우를 선택해야 될까?

 

문제에서 듀오들은 항상 최단거리로 이동한다고 했으니 s에서 진입지점까지 거리가 짧은 경우를 선택하여 답을 구하면 된다.

 

그런다음 각 경우의 "s지점에서 진입지점까지의 거리 + 탈출지점에서 목적지 후보들까지의 거리" 와 s지점에서 목적지 후보들까지의 거리를 비교했을 때 만약 s지점에서 목적지 후보까지 가는 경우 중 더 짧은 거리가 존재하면 그 목적지는 정답이 될 수 없다.

 

왜냐하면 듀오들은 항상 최단거리로 이동을 하는데 X라는 도로를 무조건 지나야 하기때문에 만약 s지점에서 목적지까지 다익스트라를 이용하여 거리를 구했을때 X도로를 거쳐가는 것보다 짧은 경우가 있으면 X도로를 거쳐가는 경우가 우회해서 가능 경우기 때문에 가능한 목적지가 될 수 없다.

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>

#define INF 987654321
#define mod 1000000
#define pii pair<int,int>

using namespace std;

vector<int> dijkstra(int n, int start, vector<vector<pii>>& graph)
{
	priority_queue<pii> pq;
	vector<int> dist(n + 1, INF);
	dist[start] = 0;
	pq.push({ 0,start });

	while (!pq.empty())
	{
		pii dt = pq.top(); pq.pop();
		int cur_node = dt.second;
		int cur_dist = -dt.first;

		for (int i = 0; i < graph[cur_node].size(); i++)
		{
			int next_node = graph[cur_node][i].first;
			int next_dist = cur_dist + graph[cur_node][i].second;

			if (dist[next_node] > next_dist)
			{
				dist[next_node] = next_dist;
				pq.push({ -next_dist, next_node });
			}
		}
	}

	return dist;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int T;
	cin >> T;
	while (T--)
	{
		int n, m, t;
		int s, g, h;
		int value;
		cin >> n >> m >> t;
		cin >> s >> g >> h;

		vector<vector<pii>> graph; graph.resize(n + 1);
		vector<int> candidate;

		int start, end, cost;
		for (int i = 0; i < m; i++)
		{	
			cin >> start >> end >> cost;
			graph[start].push_back({ end,cost });
			graph[end].push_back({ start,cost });

			if ((start == g && end == h) || (start == h && end == g)) value = cost;
		}

		int tmp;
		for (int i = 0; i < t; i++)
		{
			cin >> tmp; candidate.push_back(tmp);
		}

		priority_queue<pii> pq;
		vector<int> dist = dijkstra(n, s, graph);
		vector<int> dist_g = dijkstra(n, g, graph);
		vector<int> dist_h = dijkstra(n, h, graph);

		int sum = 0;
		vector<int> ans;
		
		if (dist[g] < dist[h])
		{
			sum += dist[g] + value;
			for (int i = 0; i < candidate.size(); i++)
			{
				if (sum + dist_h[candidate[i]] <= dist[candidate[i]]) ans.push_back(candidate[i]);
			}
		}
		else
		{
			sum += dist[h] + value;
			for (int i = 0; i < candidate.size(); i++)
			{
				if (sum + dist_g[candidate[i]] <= dist[candidate[i]]) ans.push_back(candidate[i]);
			}
		}
		
		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
		cout << "\n";
	}
}

굳