백준 9370번 : 미확인 도착지 - 다익스트라

https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

 

1.문제설명

백준 9370번

문제가 꽤 복잡하다.

 

단순하게 정리하면

시작점과 꼭 경유해야하는 간선이 주어졌을 때 해당하는 노드가

문제에서 원하는 도착점이 될 수 있는지

판단해야한다.

 

 

---

 

2.접근방법[알고리즘]

https://www.acmicpc.net/board/view/47684

글 읽기 - 이렇게 풀면 쉽지 않나요?

 

도착점 후보가 진짜로 도착점인지 확인하려면

 

시작점으로부터 경유지를 경유하고 도착점 후보에 도착한 거리와

 

시작점으로부터 도착점 후보까지의 최단 거리가 같아야한다.

 

이를 바탕으로 최단거리에 도달 했을 때 g와 h의 간선을 지났다면

 

해당 도착점후보가 도착점이 될 수 있음을 알 수 있다.

 

그래서 g-h 간선을 지났는지 여부를 따로 저장해주면서 확인하면 이 문제를 해결 할 수 있다.

 

 

 

 

다만 핵심은 priority_queue를 이용할 때

 

거리와 노드가 동일하다면 g-h간선이 지난 여부가 true인 상태가

 

우선으로 pop 되도록 설계해야 한다.

 

 

 

 

 

 

---

 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
	int x, d;
	bool ispassing;

	bool operator<(const Node& b) const {
		if (x == b.x && d == b.d) {
			return ispassing < b.ispassing;
		}
		return d > b.d;
	}

};


bool dijkstra(vector<pair<int, int> >* v, int st, int en, int g, int h) {
	bool passed = false;

	int dist[2001];
	memset(dist, 0x3f, sizeof(dist));

	priority_queue<Node> Q;
	Q.push({ st,0,0 });

	while (!Q.empty()) {
		int x = Q.top().x;
		int d = Q.top().d;
		bool p = Q.top().ispassing;

		Q.pop();

		if (dist[x] <= d) continue;
		dist[x] = d;

		if (x == en) {
			if (p) {
				passed = true;
			}

			break;
		}

		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i].first;
			int nd = d + v[x][i].second;

			if (dist[nx] > nd) {
				if (p) {
					Q.push({ nx,nd,p });
				}
				else {
					if ((x == g && nx == h) || (x == h && nx == g)) {
						Q.push({ nx,nd,1 });
					}
					else {
						Q.push({ nx,nd,0 });
					}
				}
			}

		}

	}
	return passed;
}

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

	int tt;
	cin >> tt;

	for (int T = 0; T < tt; T++) {

		vector<pair<int, int> > v[2001];

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

		for (int i = 0; i < m; i++) {
			int a, b, d;
			cin >> a >> b >> d;

			v[a].push_back({ b,d });
			v[b].push_back({ a,d });
		}

		vector<int> ans;
		for (int i = 0; i < t; i++) {
			int x;
			cin >> x;


			if (dijkstra(v, s, x, g, h)) {
				ans.push_back(x);
			}

		}

		sort(ans.begin(), ans.end());

		for (int i = 0; i < ans.size(); i++) {
			cout << ans[i] << ' ';
		}

		cout << '\n';

	}


	return 0;
}

백준 9370번