백준 9370번 [미확인 도착지](C++) -yes6686- 티스토리

[목차]

• 문제
• 소스코드

---

 

문제 링크 : https://www.acmicpc.net/problem/9370

 

 

문제를 읽어보면 s지점에 출발하여 최단경로를 구할 때  무조건 g와 h 교차로를 지나간다는 것을 알 수 있다.

이걸로 아이디어를 떠올릴 수 있다.

그렇다면 s지점에서 출발해 g지점 또는 h지점으로 가는 경우에서 만약 s->g-h, s->h-g 이 두 가지 경우의 수를 생각할 수 있다.

그렇다면! 이 두가지 경우의 수를 다시 있어가면

1. s->g-h->t(목적지 후보) 

2. s->h-g->t(목적지 후보) 

이렇게 2가지로 나뉘어진다 즉 마지막에 목적지 후보들이 g와 h 교차로를 지나가는지 확인해 줄 때 저 두 가지 경우 중 일치하는 경우가 있다면 출력시키면 된다.

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9
using namespace std;

int dis_s[2001];
int dis_h[2001];
int dis_g[2001];
priority_queue<int,vector<int>,greater<int>>desCandidateQ; //오름차순의 정수들로 출력시키기 위해
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
vector<pair<int, int>>v[2001];

void djk(int x,int dis[2001]) {
	for (int i = 1; i <= 2000; i++) {
		dis[i] = INF;
	}
	dis[x] = 0;
	pq.push({ dis[x],x});
	while (!pq.empty()) {
		int cost = pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		for (int i = 0; i<v[cur].size(); i++) {
			int ncost = v[cur][i].first;
			int next = v[cur][i].second;
			if (dis[next] > cost + ncost) {
				dis[next] = cost + ncost;
				pq.push({ dis[next],next });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n, m, t;
		cin >> n >> m >> t;
		int s, g, h;
		cin >> s >> g >> h;
		int a, b, d;
		int GHlen;
		for (int i = 0; i < m; i++) {
			cin >> a >> b >> d;
			v[a].push_back({ d,b });
			v[b].push_back({ d,a });
			if ((a == g && b == h) || (a == h && b == g)) {
				GHlen = d;
			}
		}
		djk(s, dis_s);
		djk(h, dis_h);
		djk(g, dis_g);
		int x;
		for (int i = 0; i < t; i++) {
			cin >> x;
			desCandidateQ.push(x);
		}
		while (!desCandidateQ.empty()) {
			int k = desCandidateQ.top();
			desCandidateQ.pop();
			if ((dis_s[k] == dis_s[g] + GHlen + dis_h[k]) ||
				(dis_s[k] == dis_s[h] + GHlen + dis_g[k])) {
				cout << k << ' ';
			}	
		}
		for (int i = 1; i <= n; i++) {
			v[i].clear();
		}
		cout << '\n';
	}
}

 

편하게 댓글로 질문해 주세요~