백준 9370번 미확인 도착지

오늘은 이전에 풀었던 백준 9730번 미확인 도착지에 대한 풀이를 적어 보겠습니다,
이번 문제에서는 좋았던 점이 다익스트라를 통하여 나오는 코드를 응용하면 되는 문제라
다익스트라가 언제 쓰일지에 대해서 더 감잡기 좋았던 거 같습니다, 여튼 풀이 들어가겠습니다.

일단 이 문제를 요약해보자면

서커스단은 g -> h 또는 h -> g 경로를 무조건 지나갔다는거고
이 경로를 무조건 지나가는 과정에서 여러 도착 후보지중에서 어떤 후보지가
말이 되는지..를 생각해보아야 한다

그럼 다시 도착 후보지중에서 어떤 후보지가 말이 될까?
그 답은 문제중에 있다

그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

그들은 급한 상황이기에 목적지를 "우회" 하지 않는다, 즉

G -> H or H -> G를 통해서 가는 도착지 거리 > S에서 도착지 거리

이 경로를 통해서 지나는 거리가 S에서 도착지 거리보다는 무조건 높아지면 안되고
무조건 같아야한다. (왜냐면 최단거리이니깐)

근데 나도 문제를 풀면서 들었던 의문이 만약 G -> H or H -> G를 통한길이
S부터 도착 후보지 거리보다 무조건 더 비용이 많이 드는 경우로 예시를 주면
모든 도착 후보지가 그냥 무시 되는건가? 하는 의문이 들었지만 일단 문제에서는
서커스단이 우회하지 않고 최단거리로 갈 것이라고 했기에 그냥 하면 될 것 같기도 하다

여튼 위 내용을 알았다면 문제의 절반은 푼 것이다

위 그림을 보면 앞에서 말한대로 도착지는 6번만이 될 수 없다(우회 안하고 최단거리)

그럼 특정 경로를 지나야하고 어떤 도착지 후보만 가능한지도 알았으니 추가로 어떤게 필요할까?
간단하다, S에서 시작하는 모든 최단거리 G나 H에서 시작하는 모든 최단거리를 구하고

• S -> G -> H -> D(도착지들)
• S -> H -> G -> D(도착지들)

위에 두개를 탐색하면서 아까 말했던 이 후보지가 가능한지(최단거리인지)
여부를 따지고 후보 도착지들만 출력하면 정답이다.

아래는 정답코드입니다 !!

#include <bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int>>> adj;

vector<int> dij(int s) {

	priority_queue<pair<int, int>, 
	vector<pair<int, int>>, 
	greater<pair<int, int>>> pq;
	// cost, node
	
	vector<int> dist(adj.size(), INT_MAX); // 초기화
	
	dist[s] = 0;
	
	pq.push({0, s});
	
	while(pq.size()) {
		int cost = pq.top().first;
		int now = pq.top().second;
		pq.pop();
		
		if(dist[now] < cost) continue;
		
		for(int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i].first;
			int next_cost = adj[now][i].second + cost;
			
			if(dist[next] > next_cost) {
				dist[next] = next_cost;
				pq.push({next_cost, next});
			}
		}
	}
	
	return dist;
}

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

	int t_c;
	
	cin >> t_c;
	
	while(t_c--) {
		int n, m, t;
		
		cin >> n >> m >> t;
		
		adj.clear();
		adj.resize(n + 1);
		vector<int> dest(t);
		
		int s, g, h;
		
		cin >> s >> g >> h;
		
		for(int i = 0; i < m; i++) {
			int from, to, cost;
			cin >> from >> to >> cost;
			adj[from].push_back({to, cost});
			adj[to].push_back({from, cost});
		}
		
		vector<int> dist_s = dij(s);
		vector<int> dist_g = dij(g);
		vector<int> dist_h = dij(h);
		int dist_gh = dist_g[h]; // 어차피 사이에 값은 똑같아서 하나만 있어도 됨 
		
		for(int i = 0; i < t; i++) {
			cin >> dest[i]; // 후보지 입력 
		}
		
		sort(dest.begin(), dest.end());
		
		for(int idx : dest) {
			// "최단거리" 알고리즘 이기에 우회를 안함
			// 즉 g -> h 나 h -> g를 지나는 도착지이던
			// 그런 거 없이 그냥 다익스트라던 "최단거리" 이기에 무조건 같아야함 거리는
			// 다시 말하지만 서커스 예술가들은 "우회를 안함" 
			if(dist_s[idx] == dist_s[g] + dist_gh + dist_h[idx]) cout << idx << " ";
			else if (dist_s[idx] == dist_s[h] + dist_gh + dist_g[idx]) cout << idx << " ";
		}
		cout << '\n';
	}		
	
    
    return 0;
}