[백준 9370] 미확인 도착지 (C++)

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 2147483646
using namespace std;
typedef pair<int, int>pii;


int T;
int V, E, t;
int s, g, h;
int dists[2001];
int dist[2001];
int candidate[101];
vector<pii> d[2001];     //그래프의 정보 담음
int visited[2001];
priority_queue< pii, vector<pii>, greater<pii> > pq;
// 아주 기본적인 다익스트라 

void dijkstra(int st) {
	dist[st] = 0;
	// { 거리 , 현재 vertex} 
	pq.push({ 0,st });

	while (!pq.empty()) {
		int curr = pq.top().second; // 방문한 vertex
		int currd = pq.top().first;
		visited[curr] = 1;
		pq.pop();
		// 이동후 정보 갱신
		for (auto i : d[curr]) {
			int next = i.first, nextd = i.second;
			if (dist[next] > currd + nextd && !visited[next]) {
				dist[next] = currd + nextd;
				pq.push({ dist[next], next });

			}
		}
	}

}

void clear() {
	while (!pq.empty())
	{
		pq.pop();
	}
	for (int i = 1; i <= V; i++) dist[i] = INF;
	for (int i = 0; i < 2001; i++) visited[i] = 0;
}

int pass_through(int end) {
	int path1 =INF, path2 = INF, path3 =INF;
	int course1, course2;
	//course1 먼저 구하기  (g에 먼저 방문) 
	path1 = dists[g];
	for (auto i : d[g]) {
		int next = i.first, nextd = i.second;
		if (next == h) {
			path2 = nextd;
			break;
		}
	}
	clear();
	dijkstra(h);
	path3 = dist[end];
	if (path1 == INF || path2 == INF || path3 == INF)
		course1 = INF;
	else
		course1 = path1 + path2 + path3;
	// course 2 구하기

	path1 = dists[h];
	for (auto i : d[h]) {
		int next = i.first, nextd = i.second;
		if (next == g) {
			path2 = nextd;
			break;
		}
	}
	clear();
	dijkstra(g);
	path3 = dist[end];
	if (path1 == INF || path2 == INF || path3 == INF)
		course2 = INF;
	else
		course2 = path1 + path2 + path3;

	if (course1 < course2)
		return course1;
	else
		return course2;
}


int main() {
	// V vertex의 개수 
	// Edge 의 개수 
	// K 시작 정점의 번호 
	FASTIO;
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> V >> E >> t;
		cin >> s >> g >> h;
		for (int i = 0; i < E; i++) {
			//인접 그래프 생성
			int a, b, c; cin >> a >> b >> c;
			d[a].push_back({ b,c });  // {vertex , 거리}
			d[b].push_back({ a,c });
		}
		candidate[0] = 0;
		for (int j = 1; j <= t; j++) {
			int tmp;
			cin >> tmp;
			candidate[j] = tmp;
		}
		sort(candidate, candidate + t+1);
		/*
		for (int j = 1; j <= t; j++) {
			cout << candidate[j] << " ";
		}
		cout << "\n";
		*/
		//입력 끝 알고리즘 시작 
		clear();
		dijkstra(s);
		// 기본적으로 출발지에서 다익스트라를 사용하고 시작 
		for (int i = 1; i <= V; i++) {
			dists[i] = dist[i];
		}
		for (int j = 1; j <= t; j++) {
			int ans = pass_through(candidate[j]);
			if (dists[candidate[j]] == INF)
				continue;
			if (ans == dists[candidate[j]])
				cout << candidate[j] << " ";
		}
		//cout <<"test case end "<< "\n";

		for (int j = 1; j <= t; j++) {
			candidate[j] = 0;
		}
		for (int i = 1; i <= V; i++) {
			dists[i] = 0;
		}

		for (int i = 0; i <= V; i++) {
			d[i].clear();
		}

		cout << "\n";
	}
}

출발지에서 후보 도착지 까지의 최단거리 와 

출발지 -> g -> h -> 후보 도착지 or 출발지 -> h -> g -> 후보 도착지 의 최단 거리가 

같은 경우 

 

즉 출발지 -> 후보 도착지 == min (출발지 -> g -> h -> 후보 도착지 ,출발지 -> h -> g -> 후보 도착지)

인 경우 후보 도착지에 도달 할 수 있게 된다.

 

여기서 간과했던 점은 이 부분이다. 

도착지에 가는것이 아예 불가능 한 경우에도 위의 조건을 충족하는데

이 점을 고려하지 않아서 틀렸었다.

 

아래 코드를 추가하여 해결하였다.

if (dists[candidate[j]] == INF)
	continue;