BOJ 9370 미확인 도착지

www.acmicpc.net/problem/9370

9370번: 미확인 도착지

 

• 첫 번째 줄에 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와 같지 않다.

뭐가 많이 주어져서 읽기 싫어지게 하는 문제였다. 잘 읽고 이해해보면

시작 노드 s에서 도착지 후보에서의 거리 x가

g -> h 나 h -> g를 경유한 값과 똑같다면 출력해주면 된다.

 

처음에는 dist배열 하나로 접근했는데 생각해보니 n의 총개수가 2000개라 

S, G, H 총 3개를 다익스트라를 써도 6000이라 한번에 구해놓고 목적지 후보를 받아줬다.

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e9;
int tc, n, m, t, s, g, h, a, b, d, x;
priority_queue<pair<int, int>> pq;
vector<pair<int, int>> ar[2001];

vector<int> dijkstra(int s) {
	vector<int> d(n, INF);
	d[s] = 0;
	pq.push({ 0,s });

	while (!pq.empty()) {
		int cur = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if (d[cur] < cost) continue;
		for (auto& i : ar[cur]) {
			int nc = i.second + cost;
			if (nc < d[i.first]) {
				d[i.first] = nc;
				pq.push({ -nc,i.first });
			}
		}
	}

	return d;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> tc;

	while (tc--) {
		vector<int> path, S, G, H;
		for (int i = 0; i < 2001; ++i) ar[i].clear();

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

		for (int i = 0; i < m; ++i) { //무항향 그래프
			cin >> a >> b >> d;
			ar[a - 1].push_back({ b - 1,d });
			ar[b - 1].push_back({ a - 1,d });
		}

		S = dijkstra(s - 1);
		G = dijkstra(g - 1);
		H = dijkstra(h - 1);

		while (t--) {
			cin >> x;
			if (S[x - 1] == S[g - 1] + G[h - 1] + H[x - 1] || S[x - 1] == S[h - 1] + H[g - 1] + G[x - 1])
				path.push_back(x);
		}
		sort(path.begin(), path.end());
		for (auto i : path) cout << i << ' ';
		cout << '\n';
	}

	return 0;
}

 

S, G, H 배열은

각각 s에서 시작한 최단거리, g에서 시작한 최단거리, h에서 시작한 최단거리이다.