[알고리즘] 백준 9370번: 미확인 도착지 (C++)

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

9370번: 미확인 도착지

[방법]

s->g->h->x or s->h->g->x가 s->x로 가는 경로 중에 최단 경로여야 한다.

가중치 모두 양수이므로 다익스트라 알고리즘이 사용 가능하다.

 

(경로를 구하는 방식은 이 문제를 통해 공부를 했었다. https://draw-code-boy.tistory.com/138)

int path1_1 = fromS[g] + fromG[h] + fromH[x];
int path1_2 = fromS[h] + fromH[g] + fromG[x];
int path1 = min(path1_1, path1_2);

int path2 = fromS[x];

헷갈렸던 이유 (독해의 오류)

path1이 path2보다 커야 그 목적지 후보(x)가 목적지가 될 수 있다고 조건을 달아주어 버렸다.

if (path1 > path2) {
	result.push_back(x);
}

그 반대여야 한다. path1이 g와 h를 포함하므로 path1이 s에서 x로 가는 경로 중 제일 최단 경로가 되어야 한다.

그래서 s->x로 가는 경로 중 제일 최단 경로로 구한 path2와 path1이 같아야 한다.

 

[AC 코드]

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#define MAX 2000 + 1
#define INF 987654321
using namespace std;

int T;
vector<pair<int, int>> graph[MAX];

struct cmp {
	bool operator()(pair<int, int>& a, pair<int, int>& b) {
		return a.second > b.second;
	}
};

vector<int> dijkstra(int node, int n) {
	vector<int> dist(n + 1, INF);
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	dist[node] = 0;
	pq.push(make_pair(node, 0));
	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;

		pq.pop();
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push(make_pair(next, dist[next]));
			}
		}
	}

	return dist;
}

void resetGraph(int n) {
	for (int i = 1; i <= n; i++) {
		while (!graph[i].empty()) {
			graph[i].pop_back();
		}
	}
	return;
}

int main() {
	cin >> T;
	for (int test = 0; test< T; test++) {
		int n, m, t;
		cin >> n >> m >> t; // n == 노드 개수, m == 간선 개수, t == 목적지 후보 개수

		int s, g, h;
		cin >> s >> g >> h; // s == 출발지, g, h == 거치는 필수 노드
		for (int i = 0; i < m; i++) {
			int a, b, d;
			cin >> a >> b >> d;
			graph[a].push_back(make_pair(b, d));
			graph[b].push_back(make_pair(a, d));
		}

		vector<int> fromS = dijkstra(s, n);
		vector<int> fromG = dijkstra(g, n);
		vector<int> fromH = dijkstra(h, n);

		vector<int> result;

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

			int path1_1 = fromS[g] + fromG[h] + fromH[x];
			int path1_2 = fromS[h] + fromH[g] + fromG[x];
			int path1 = min(path1_1, path1_2);

			int path2 = fromS[x];
			//cout << path1 << ' ' << path2 << '\n';
			if (path1 == path2) {
				result.push_back(x);
			}
		}

		sort(result.begin(), result.end());
		for (int i = 0; i < result.size(); i++) {
			cout << result[i] << ' ';
		}
		cout << '\n';
		
		resetGraph(n);
	}
	return 0;
}