BOJ - 9370번 미확인 도착지 (C++)

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

문제 난이도

Gold 2

문제 접근법

다익스트라를 이용해서 시작 정점에서 시작해 각 정점까지의 최단 거리를 구한다.
그 후, 꼭 지나야하는 g,h 정점을 mid1,2 변수로 두고 더 최단거리가 작은 정점을 mid1에 둔다.
왜냐하면, s -> g가 2이고 s->h가 4이면 s -> g -> h -> t 여야 하기 때문이다.
그래서 s -> g, g->h, h->t 까지의 거리들 값이 s->t 값이 같으면 출력한다.

통과 코드

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

#define INF 987654321

using namespace std;

vector<pair<int,int>> arr[2001];

vector<int> dijkstra(int start,int n) {
	vector<int> dp(n + 1, INF);
	dp[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
	pq.push({ 0,start });
	while (!pq.empty()) {
		int now = pq.top().second;
		int dis = pq.top().first;
		pq.pop();
		if (dis > dp[now]) continue;
		for (int i = 0; i < arr[now].size(); i++) {
			int next = arr[now][i].first;
			int nDis = arr[now][i].second;
			if (dp[next] > nDis + dis) {
				dp[next] = nDis + dis;
				pq.push({ dp[next], next });
			}
		}
	}
	return dp;
}

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int n, m, t, s, g, h,distMid=0;
		cin >> n >> m >> t >> s >> g >> h;
		for (int i = 0; i <= n; i++) arr[i].clear();
		for (int i = 0; i < m; i++) {
			int a, b, d;
			cin >> a >> b >> d;
			arr[a].push_back({ b,d });
			arr[b].push_back({ a,d });
			if ((a == g && b == h) || (a == h && b == g)) distMid = d;
		}
		vector<int> dist(t);
		for (int i = 0; i < t; i++) {
			cin >> dist[i];
		}
		sort(dist.begin(), dist.end());
		vector<int> dp = dijkstra(s, n);
		int mid1 = 0, mid2 = 0;
		if (dp[g] > dp[h]) {
			mid1 = h;
			mid2 = g;
		}
		else {
			mid1 = g;
			mid2 = h;
		}
		vector<int> dp2 = dijkstra(mid2, n);
		for (int i = 0; i < t; i++) {
			if (dp[dist[i]] == dp[mid1] + dp2[dist[i]] + distMid) {
				cout << dist[i] << " ";
			}
		}
		cout << "\n";
	}
	return 0;
}

피드백

처음에 다익스트라를 4번 썼다가 답이 안나와서 다른 사람 코드를 참고했다. 그 결과, 2번으로도 충분히 답을 구할 수 있음을 알았다!