백준 BOJ 9370 - 미확인 도착지

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

9370번: 미확인 도착지

다익스트라 문제인데

아니 이걸 왜이렇게 오래 뇌절을 쳤는지 모르겠다 엉엉엉

 

시작점 S에서 이동하는 서커스 예술가가 갈 목적지 후보 중에서

G-H간 도로를 건너 이동해야 하는 경로를 구하는 문제.

 

즉, 목적지 후보를 K라 할때,

S-K 로 이동하는 최단경로가

S-G-H-K 이거나

S-H-G-K 이면 가능한 경우에 해당하고,

 

S-K로 이동하는 최단경로의 길이가

S-G-H-K 이거나

S-H-G-K 로 이동한 최단경로의 길이보다 짧은 경우에는

G-H를 거쳐 이동하지 않았기 때문에 불가능한 경우에 해당한다.

 

테스트케이스가 있는 문제라서

1. 초기화도 꼼꼼하게 해줘야 하고

2. 메모리 초과 / 시간초과 안나게 관리 잘해줘야 한다.

 

메모리초과의 경우는 전역변수로 한번만 선언해주는 방법을 사용하면 되고,

시간초과의 경우는 목적지 후보 K에 대한 다익스트라를 돌리지 말고

 

S, H, G 세 위치에 대한 다익스트라를 돌려서

이 값들을 모두 배열에 저장해둔 뒤

배열만 탐색하면서 체크해주면 된다.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
#define x first
#define y second
#define INF 998244353
using namespace std;

int N,M,T;
int S,G,H;
int GHval;

vector<int> dest;
vector<pair<int,int>> g[2345];
priority_queue<pair<int,int>> pq;

int fromS[2345];
int fromG[2345];
int fromH[2345];

void dijkstra(int start, int *ans){
	for(int i=0; i<2345; i++) ans[i] = INF;
	
	ans[start] = 0;
	pq.push({0,start});
	
	while(!pq.empty()){
		int now =  pq.top().y;
		int dis = -pq.top().x;
		pq.pop();
		
		if(ans[now] < dis) continue;
		
		for(auto next : g[now]){
			if(ans[next.x] > dis + next.y){
				ans[next.x] = dis + next.y;
				pq.push({-(dis+next.y), next.x});
			}
		}
	}
	return;
}

int main(){
	int t;
	int a,b,x;
	cin >> t;
	while(t--){
		for(int i=0; i<2345; i++) g[i].clear();
		dest.clear();
		
		cin >> N >> M >> T;
		cin >> S >> G >> H;
		for(int i=0; i<M; i++){
			cin >> a >> b >> x;
			g[a].push_back({b,x});
			g[b].push_back({a,x});
			if(a == G && b == H) GHval = x;
			if(b == G && a == H) GHval = x;
		}
		
		for(int i=0; i<T; i++){
			cin >> x;
			dest.push_back(x);
		}
		
		sort(dest.begin(), dest.end());
		
		dijkstra(S, fromS);
		dijkstra(G, fromG);
		dijkstra(H, fromH);
		
		for(int K : dest){
			bool flag = false;		
			if(fromS[K] == fromS[G] + GHval + fromH[K]) flag = true; // S G H K
			if(fromS[K] == fromS[H] + GHval + fromG[K]) flag = true; // S H G K 
			if(flag == true){ cout << K << " "; }
		}
		cout << "\n";
	}
	return 0;
}