[백준/BOJ] 백준 9370번 : 미확인 도착지

www.acmicpc.net/problem/9370

9370번: 미확인 도착지

우선 시작 지점에서 각각 지점까지 다익스트라 알고리즘을 통해 최단경로를 구한다, 그리고 어떤 지점에서 어떤 지점으로 가는 최단 경로의 길이를 구하는 Find_dist함수를 만들어서 이를 통해 목적지 후보들 중 시작점에서 목적지까지 거리가 시작점에서 g까지의 거리 + g, h의 거리 + h에서 목적지까지 거리 또는 시작점에서 h까지의 거리 + h, g의 거리 + g에서 목적지까지 거리인지 확인한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int test_case;
int n, m, t;
int s, g, h;
int a, b, d;
int x;
int g_h_len;
vector<pair<int, int>> adj[2001]; //pair : 길이, 목적지
vector<int> dest_temp;
vector<int> result;

void Pre()
{
	result.clear();
	dest_temp.clear();

	for (int i = 0; i < 2001; i++)
		adj[i].clear();
}

//start에서 dest으로 가는 최단경로
int Find_dist(int start, int dest)
{
	priority_queue<pair<int, int>> pq;
	vector<int> short_dist(n + 1, 987654321);

	short_dist[start] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		if (here_cost > short_dist[here])
			continue;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			if (there_cost < short_dist[there])
			{
				short_dist[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}

		}
	}

	return short_dist[dest];
}

vector<int> Solve(int start)
{
	priority_queue<pair<int, int>> pq;
	vector<int> short_dist(n + 1, 987654321); //start에서 각 지점으로의 최단경로

	short_dist[start] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		if (here_cost > short_dist[here])
			continue;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			if (there_cost < short_dist[there])
			{
				short_dist[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}

		}
	}

	vector<int> ret;

	//목적지 후보들 중 확인
	for (int i = 0; i < dest_temp.size(); i++)
	{
		int g_dest_len = Find_dist(g, dest_temp[i]);
		int h_dest_len = Find_dist(h, dest_temp[i]);

		//시작점에서 목적지 까지 거리가 시작점에서 g까지의 거리 + g,h의 거리 + h에서 목적지까지 거리 또는 시작점에서 h까지의 거리 + h,g의 거리 + g에서 목적지까지 거리인지 확인 
		if ((short_dist[dest_temp[i]] == short_dist[g] + g_h_len + h_dest_len) || (short_dist[dest_temp[i]] == short_dist[h] + g_h_len + g_dest_len))
			ret.push_back(dest_temp[i]);
	}

	return ret;
}

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

	cin >> test_case;

	for (int tc = 0; tc < test_case; tc++)
	{
		Pre();

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

		for (int i = 0; i < m; i++)
		{
			cin >> a >> b >> d;
			adj[a].push_back(make_pair(d, b));
			adj[b].push_back(make_pair(d, a));

			if ((a == g && b == h) || (a == h && b == g))
				g_h_len = d; //g-h의 길이 저장
		}

		for (int i = 0; i < t; i++)
		{
			cin >> x;
			dest_temp.push_back(x); //목적지 후보들 저장
		}

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

		result = Solve(s);

		for (int i = 0; i < result.size(); i++)
			cout << result[i] << " ";
		cout << "\n";
	}



	return 0;
}