미확인 도착지 (feat. 백준, 9370번)

미확인 도착지
https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
set<pair<int, int>> arr[2001];
int ans[2001];
void solution(register int n, register int start) {
	for (register int i = 1; i <= n; ++i)
		ans[i] = static_cast<int>(1e8);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push(make_pair(0, start));
	ans[start] = 0;
	while (!q.empty()) {
		auto v = q.top(); q.pop();
		auto x = v.second, c1 = v.first;
		if (ans[x] < c1)
			continue;
		for (auto iter = arr[x].begin(); iter != arr[x].end(); ++iter) {
			auto y = iter->first, c2 = iter->second;
			if (ans[y] > c1 + c2)
				ans[y] = c1 + c2, q.push(make_pair(ans[y], y));
		}
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int T;
	cin >> T;
	for (register int test = 0, n, m, t, s, g, h; test < T; ++test) {
		cin >> n >> m >> t >> s >> g >> h;
		for (register int i = 1; i <= n; ++i)
			arr[i].clear();
		for (register int mm = 0, a, b, d; mm < m; ++mm)
			cin >> a >> b >> d, arr[a].insert(make_pair(b, d)), arr[b].insert(make_pair(a, d));
		set<int> tmp;
		for (register int tt = 0, e; tt < t; ++tt)
			cin >> e, tmp.insert(e);
		for (auto& e : tmp) {
			solution(n, s);
			auto se = ans[e], sg = ans[g], sh = ans[h];
			solution(n, g);
			auto gh = ans[h], ge = ans[e];
			solution(n, h);
			auto hg = ans[g], he = ans[e];
			auto sghe = sg + gh + he;
			auto shge = sh + hg + ge;
			if (se == sghe || se == shge)
				cout << e << " ";
		}
		cout << "\n";
	}
	return 0;
}
// *&)*@*

이전 '특정한 최단 경로' 와 같이 반드시 거쳐야하는 노드를 통해 정답을 구하는 방식입니다.

특정한 최단 경로 (feat. 백준, 1504번)

시작점 s, 반드시 거쳐야하는 지점 g h, 도착점 e 가 있을때 s->g, g->h, h->e 와 s->h, h->g, g->e 중 s->e로의 값과 같으면 도착점 e는 목적지라고 볼 수 있습니다.

왜냐하면 두 값이 같다면 최단 경로라고 볼 수 있기 때문입니다.