BOJ 9370 미확인 도착지

1 개요

BOJ 9370 미확인 도착지

• 백준 온라인 저지 9370번 문제
• BOJ 32단계

2 C++

#include <bits/stdc++.h>
#include <limits.h>
using namespace std;

int n, m, t;
int s, g, h;
vector<pair<int,int>> arr[2001];
vector<int> xx;
int dotted;

vector<int> dijkstra(int start, int num) {
	vector<int> visited(num+1, INT_MAX);
	visited[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
	pq.push({0, start});
	int x, dist, nx, ndist;
	while (!pq.empty()) {
		x = pq.top().second;
		dist = pq.top().first;
		pq.pop();
		for (int i=0; i<arr[x].size(); i++) {
			nx = arr[x][i].first;
			ndist = arr[x][i].second;
			if (dist + ndist >= visited[nx]) continue;
			visited[nx] = ndist + dist;
			pq.push({visited[nx], nx});
		}
	}
	return visited;
}

void solve() {
    sort(xx.begin(), xx.end());
	vector<int> visited1 = dijkstra(s, n);
	int mid1, mid2;
	if (visited1[g] > visited1[h]) {
		mid1 = h;
		mid2 = g;
	} else {
		mid1 = g;
		mid2 = h;
	}
	vector<int> visited2 = dijkstra(mid2, n);
	for (int i=0; i<t; i++) {
		if (visited1[xx[i]] == visited1[mid1] + visited2[xx[i]] + dotted) {
			cout << xx[i] << ' ';
		}
	}
	cout << '\n';
}

void testcase() {
	for (int i=0; i<=n; i++) {
	    arr[i].clear();
	}
	cin >> n >> m >> t;
	cin >> s >> g >> h;
	int a, b, d;
	for (int i=0; i< m; i++) {
		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)) dotted = d;
	}
	xx.clear();
	int temp;
	for (int i=0; i<t; i++) {
		cin >> temp;
		xx.push_back(temp);
	}
	solve();
}

int main() {
	int T;
	cin >> T;
	while (T--) {
	    testcase();
	}
}