[백준 9370] 미확인 도착지

요구사항

그래프에서 주어진 엣지를 포함하여 도착점까지 최단 경로로 갈 수 있는지 구하기

 

풀이

시작점 -> 도착점 까지 가는 경우는

S>G>H>E

S>H>G>E 

주어진 엣지를 포함하여 E까지 도달하는 경우의 수는 2가지 이다

 

S에서 다익스트라

G에서 다익스트라

H에서 다익스트라

 

실시하여 S에서 E까지의 거리와 각 경로의 거리 합이 같으면 정답을 출력한다

 

#pragma warning(disable:4996)
#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <functional>
using namespace std;

int n, m, t, s, g, h;
struct go {
	int x;
	int y;
};
vector<go> graph[2020];
vector<int> destination;
int dist[2020];
void dijkstra(int start) {
	for (int i = 1; i <= n; i++) dist[i] = 987654321;
	dist[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > q;
	q.push({ 0,start });

	while (!q.empty()) {
		int nownode = q.top().second;
		int nowdist = q.top().first;
		q.pop();

		for (int i = 0; i < graph[nownode].size(); i++) {
			int nextnode = graph[nownode][i].x;
			int nextdist = graph[nownode][i].y;

			if (dist[nextnode] > nowdist + nextdist) {
				dist[nextnode] = nowdist + nextdist;
				q.push({ dist[nextnode],nextnode });
			}

		}
	}
}
bool com(go a, go b) {
	if (a.x < b.x) return true;
	else if (a.x == b.x) {
		if (a.y < b.y) return true;
	}
	return false;
}
int main() {
	int t;
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		scanf("%d%d%d%d%d%d", &n, &m, &t, &s, &g, &h);
		int ghdist = 0;
		for (int i = 1; i <= n; i++)	graph[i].clear();
		for (int i = 0; i < m; i++) {
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			graph[x].push_back({ y,z });
			graph[y].push_back({ x,z });
			if (x == g && y == h) {
				ghdist = z;
			}
			if (x == h && y == g) {
				ghdist = z;
			}
		}
		//cout << "A" << ghdist << endl;
		for (int i = 0; i < t; i++) {
			int x;
			scanf("%d", &x);
			destination.push_back(x);
		}

		//1번째로 s>g>h>t
		dijkstra(s);
		int Sdist[2020];
		for (int i = 1; i <= n; i++) Sdist[i] = dist[i];
		//g h 까지의 거리
		int hdist = dist[h];
		int gdist = dist[g];

		//g에서 t까지의 최소 거리들
		dijkstra(g);
		int Gdist[2020];
		for (int i = 1; i <= n; i++) Gdist[i] = dist[i];
		//h에서 t까지의 최소 거리들
		dijkstra(h);
		int Hdist[2020];
		for (int i = 1; i <= n; i++) Hdist[i] = dist[i];
		sort(destination.begin(), destination.end());
		for (int i = 0; i <destination.size(); i++) {
			int now = destination[i];
			int G = Gdist[now] + gdist + ghdist;
			int H = Hdist[now] + hdist + ghdist;
		//	cout << Gdist[now] << " " << Sdist[g] << " " << Sdist[h] << endl;
			//cout << "now " << now << " " << Sdist[now] << " " << G << " " << H << endl;
			if (Sdist[now] == Hdist[now] + Sdist[g] + ghdist) printf("%d ", now);
			else if (Sdist[now] == Gdist[now] + Sdist[h] + ghdist) printf("%d ", now);
		}
		printf("\n");
		destination.clear();

	}
}