[BOJ] 9370 : Destination Unknown

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

---

최단경로 다익스트라

 시작지점 S에서 최단거리로 도착 후보 지점으로 갈 때, 최단 경로에 G-H 교차로가 포함되어있다면 우리가 원하는 정답이다. 어렵게 생각하지말고, S 에서 어떤 목적지 D로 가는 최단 거리가 S에서 G로가는 최단거리 + G에서 H로 가는 최단거리 + H에서 D로가는 최단거리와 같거나 반대로 S에서 H로 가는 최단거리 + H에서 G로 가는 최단 거리 + G 에서 D로가는 최단거리와 같은지 체크하면 된다.

 따라서, 다익스트라 알고리즘을 이용해 시작지점 S / G / H 에서 각각 다른 모든 정점과의 최단 거리를 구하면 된다.

#include<iostream>
#include<queue>
#include<algorithm>

#define INF 999999999
using namespace std;

vector<int> dijkstra(vector<pair<int, int>> graph[2001], int n , int s) {
	priority_queue<pair<int, int>> pq;
	vector<int> distance(n + 1, INF);
	distance[s] = 0;
	pq.push({ 0, s });
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if (distance[here] < cost) continue;
		for (int i = 0; i < graph[here].size(); i++) {
			int next = graph[here][i].first;
			int nextDist = graph[here][i].second + cost;
			if (distance[next] > nextDist) {
				distance[next] = nextDist;
				pq.push({ -nextDist, next });
			}
		}
	}
	return distance;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int T;
	cin >> T;
	while (T--) {
		int n, m, t, s, g, h;
		cin >> n >> m >> t >> s >> g >> h;

		vector<pair<int, int>> graph[2001];
		vector<int> destination(t);
		for (int i = 0, a, b, d; i < m; i++) {
			cin >> a >> b >> d;
			graph[a].push_back({ b, d });
			graph[b].push_back({ a, d });
		}
		for (int i = 0; i < t; i++)
			cin >> destination[i];

		vector<int> distanceS = dijkstra(graph, n, s);
		vector<int> distanceG = dijkstra(graph, n,g);
		vector<int> distanceH = dijkstra(graph, n,h);

		sort(destination.begin(), destination.end());
		for (int i = 0; i < t; i++) {
			if (distanceS[destination[i]] != INF && distanceS[g] + distanceG[h] + distanceH[destination[i]] == distanceS[destination[i]])
				cout << destination[i] << ' ';
			else if (distanceS[destination[i]] != INF && distanceS[h] + distanceH[g] + distanceG[destination[i]] == distanceS[destination[i]])
				cout << destination[i] << ' ';
		}
		cout << '\n';
	}
}

---