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

문제

 

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

9370번: 미확인 도착지

---

Algorithm

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

• gh​를 지나는 경로의 경우는 다음과같다.

1. (출발점) → g → h → (목적지)
2. (출발점) → h → g → (목적지)

• 즉, 출발점에서 목적지에 가는 최단경로의 길이를 구해둔 뒤 다음과같이 작업한다.
  1. 출발점에서 g까지의 최단경로를 구한다.
  2. 출발점에서 h까지의 최단경로를 구한다.
  3. g에서 목적지까지의 최단경로를 구한다.
  4. h에서 목적지까지의 최단경로를 구한다.
     
     
  • (1 + gh​ + 3)의 길이와 미리 구해둔 출발점에서 목적지에 가는 최단경로의 길이가 동일하면 가능한 후보이다.
  • (2 + gh​ + 4)의 길이와 미리 구해둔 출발점에서 목적지에 가는 최단경로의 길이가 동일하면 가능한 후보이다.
  • 이를 위해 gh​의 거리를 -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();
}