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

출력

테스트 케이스마다

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

 

 

다익스트라 알고리즘.

각 조건에 맞게 그래프를 만들고, 출발 노드, 거치는 노드를 입력받아온다.

 

이제 2가지의 경우를 생각한다.

1) s -> g -> h -> 목적지

2) s -> h -> g -> 목적지

 

ans1은 s->g->h까지의 최단 경로,

ans2는 s->h->g까지의 최단 경로를 나타낸다.

 

두 경우를 구한 뒤 목적지까지의 최단 경로를 한번 더 구하면 된다.

목적지는 후보가 여러 개 있으므로 destination 벡터에 담아 for문으로 순회.

 

for문 안에서

tmp1은 s->g->h->목적지까지의 최단 경로,

tmp2는 s->h->g->목적지까지의 최단 경로를 나타낸다.

 

이 두 값이 INF보다 작으면 가능하다는 뜻이다.

그렇다면 tmp1과 tmp2 중 값이 작으면서 s->목적지까지의 최단 경로보다 값이 작거나 같은 경우가 answer에 들어간다.

그 후 answer를 오름차순으로 정렬하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 1000000000

using namespace std;

int dijkstra(int start, int end, vector<pair<int, int>> *graph){
	priority_queue<pair<int, int>> pq;
	vector<int> dist(2001, INF);
	
	pq.push(make_pair(0, start));
	dist[start] = 0;

	while(!pq.empty()){
		int cost = -pq.top().first;
		int current = pq.top().second;

		pq.pop();

		if(dist[current] < cost){
			continue;
		}

		for(int i = 0; i < graph[current].size(); i++){
			int next = graph[current][i].first;
			int nextCost = graph[current][i].second + cost;

			if(dist[next] > nextCost){
				dist[next] = nextCost;
				pq.push(make_pair(-nextCost, next));
			}
		}
	}
	return dist[end];
}

int main(void){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;

	cin >> T;

	while(T--){
		int n, m, t, s, g, h;
		long long ans1 = 0, ans2 = 0;
		priority_queue<pair<int, int>> pq;
		vector<pair<int, int>> graph[2001];
		vector<int> destination;
		vector<int> answer;

		cin >> n >> m >> t;
		cin >> s >> g >> h;

		while(m--){
			int a, b, d;

			cin >> a >> b >> d;

			graph[a].push_back(make_pair(b, d));
			graph[b].push_back(make_pair(a, d));
		}

		while(t--){
			int x;

			cin >> x;

			destination.push_back(x);
		}

		ans1 += dijkstra(s, g, graph);
		ans1 += dijkstra(g, h, graph);

		ans2 += dijkstra(s, h, graph);
		ans2 += dijkstra(h, g, graph);
		
		for(int i = 0; i < destination.size(); i++){
			long long tmp1, tmp2;

			tmp1 = ans1 + dijkstra(h, destination[i], graph);
			tmp2 = ans2 + dijkstra(g, destination[i], graph);
			
			if(tmp1 < INF || tmp2 < INF){
				if(tmp1 < tmp2 && tmp1 <= dijkstra(s, destination[i], graph)){
					answer.push_back(destination[i]);
				}
				else if(tmp2 < tmp1 && tmp2 <= dijkstra(s, destination[i], graph)){
					answer.push_back(destination[i]);
				}
			}
		}

		sort(answer.begin(), answer.end());

		for(int i = 0; i < answer.size(); i++){
			cout << answer[i] << " ";
		}

		cout << endl;
	}

	return 0;
}