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

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
 
using namespace std;
 
int T, n, m, t, s, g, h;
int a, b, d, temp;
 
set<int> destin; 
int dist_s[2001];
int dist_g[2001];
int dist_h[2001];
vector<pair<int, int>> arr[2001];
 
void dijkstra(int start, int* dist) 
{
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pri_que;
	pri_que.push({ 0, start });
	dist[start] = 0;
 
	while (!pri_que.empty()) 
	{
		int cost = pri_que.top().first;
		int now = pri_que.top().second;
		pri_que.pop();
 
		for (int i = 0; i < arr[now].size(); ++i)
		{
			int beforeCost = dist[arr[now][i].first];
			int nextCost = cost + arr[now][i].second;
 
			if (beforeCost > nextCost)
			{
				dist[arr[now][i].first] = nextCost;
				pri_que.push({ nextCost, arr[now][i].first });
			}
		}
	}
}
 
int main() 
{
	cin >> T;
 
	while (T--) 
	{
		cin >> n >> m >> t;
		cin >> s >> g >> h;
 
		destin.clear();
 
		for (int i = 1; i <= 2000; ++i) 
		{
			arr[i].clear();
			dist_s[i] = 2000000001;
			dist_g[i] = 2000000001;
			dist_h[i] = 2000000001;
		}
 
		for (int i = 0; i < m; ++i) 
		{
			cin >> a >> b >> d;
			arr[a].push_back({ b, d });
			arr[b].push_back({ a, d });
		}
 
		for (int i = 0; i < t; ++i) 
		{
			cin >> temp;
			destin.insert(temp);
		}
 
		dijkstra(s, dist_s);
		dijkstra(g, dist_g);
		dijkstra(h, dist_h);
 
		for (int iter : destin)
		{
			if (dist_s[iter] == (dist_s[g] + dist_g[h] + dist_h[iter]))
				cout << iter << ' ';
 
			else if (dist_s[iter] == (dist_s[h] + dist_h[g] + dist_g[iter]))
				cout << iter << ' ';
		}
 
		cout << "\n";
	}
 
	return 0;
}

이 문제는 다익스트라자 알고리즘을 사용해야했습니다.

g-h 라인을 무조건 지나야 하기 때문에 s - g - h - x 가 더 빠른가 s - h - g - x 가 더 빠른가 확인 해야합니다.

그렇기 때문에 s에서 최소 거리, g에서의 최소거리, h에서의 최소거리를 찾습니다.

그후 s -> g + g ->h + h -> x 가 최소거리인지, s-> h + h ->g + g -> x가 최소거리인지 확인합니다.