Koala - 9기/코딩테스트 준비 스터디

[백준/C++] 9370번 미확인 도착지

Kim Doo Hyeon 2023. 2. 19. 01:14

문제

 

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

 

9370번: 미확인 도착지

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서

www.acmicpc.net


Algorithm

다익스트라 문제이다.
 의 교차로()를 지난 경로는 최단경로여야 하므로,
(출발점에서 목적지에 가는 최단경로의 길이) = (출발점에서  지나 목적지에 가는 최단경로의 길이) 이어야한다.

  • 를 지나는 경로의 경우는 다음과같다.
  1. (출발점)      (목적지)
  2. (출발점)      (목적지)
  • 즉, 출발점에서 목적지에 가는 최단경로의 길이를 구해둔 뒤 다음과같이 작업한다.
    1. 출발점에서 까지의 최단경로를 구한다.
    2. 출발점에서 까지의 최단경로를 구한다.
    3. 에서 목적지까지의 최단경로를 구한다.
    4. 에서 목적지까지의 최단경로를 구한다.

    • (1 +  + 3)의 길이와 미리 구해둔 출발점에서 목적지에 가는 최단경로의 길이가 동일하면 가능한 후보이다.
    • (2 +  + 4)의 길이와 미리 구해둔 출발점에서 목적지에 가는 최단경로의 길이가 동일하면 가능한 후보이다.
    • 이를 위해 의 거리를 -1로 설정하여 여러 번 건너는 것을 방지한다.

  • 중복 제거와 오름차순 출력을 동시에 해결하기 위해 set 자료구조를 활용해 답안을 출력한다.

 


 

 

Code

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int tc,n,m,t;
int s,g,h;
typedef pair<int,int> pii;
vector<pii> graph[2001];
int candi[101];//목적지 후보

int origin[2001];//최단 경로
int dist[2001];//g h를 반드시 지나는 최단 경로


void INPUT()
{
	IAMFAST
	cin >> tc;
}

void Init()
{
	for(int i = 1; i <= 2000; i++) graph[i].clear();
}

int Disconnect()
{
	int rtn;
	for(int i = 0; i < graph[g].size(); i++)
		if(graph[g][i].first == h)
			rtn = graph[g][i].second,
			graph[g][i].second = -1;
	for(int i = 0; i < graph[h].size(); i++)
		if(graph[h][i].first == g)
			graph[h][i].second = -1;
	return rtn;
}

void ijk(int start)
{
	fill(dist+1,dist+n+1,2e9);
	priority_queue<pii> pq;
	pq.push({0,start});
	dist[start] = 0;

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

		for(int i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i].first;
			int d2 = graph[now][i].second;
			if(d2 == -1) continue;

			if(dist[next] > d1 + d2)
			{
				dist[next] = d1+d2;
				pq.push({ -(d1+d2), next });
			}
		}
	}

}

void SOLVE()
{
	while(tc--)
	{
		Init();

		//Input
		cin >> n >> m >> t;
		cin >> s >> g >> h;
		for(int i = 0; i < m; i++)
		{
			int a,b,d; cin >> a >> b >> d;
			graph[a].emplace_back(b,d);
			graph[b].emplace_back(a,d);
		}
		for(int i = 0; i < t; i++) cin >> candi[i];

		//Solve
		ijk(s);
		int toG = dist[g];
		int toH = dist[h];
		for(int i = 1; i <= n; i++) origin[i] = dist[i];

		//g-h 경로 차단
		int connect = Disconnect();

		set<int> ans;
		ijk(g);
		for(int i = 0; i < t; i++)
			if(dist[candi[i]] != 2e9)
				if(origin[candi[i]] == toH + connect + dist[candi[i]])
					ans.insert(candi[i]);
		ijk(h);
		for(int i = 0; i < t; i++)
			if(dist[candi[i]] != 2e9)
				if(origin[candi[i]] == toG + connect + dist[candi[i]])
					ans.insert(candi[i]);

		//Output
		set<int>::iterator it;
		for(it = ans.begin(); it != ans.end(); it++)
			cout << *it << " ";
		cout << '\n';
	}

}

int main()
{
	INPUT();
	SOLVE();
}