[백준] 9370-미확인 도착지(C++)

문제링크: https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

 

다익스트라 + 구현 문제 

 

접근방식

 

1. 최단 거리 탐색에서 다익스트라로 구현하면 되겠다 생각

 

2. 아래 문제와 비슷한 방식

https://gusdnr69.tistory.com/239?category=799066 

[백준] 1504-특정한 최단 경로(C++)

결국 s -> g -> h -> 목표 지점 또는 s -> h -> g -> 목표 지점으로 이동할 때의 최소값이 

s -> 목표지점으로 도달하는 값이 똑같은지 비교하는 문제 

 

3. 다익스트라를 3번 호출해서 구현하자 

 

 

 

문제풀이 

 

1. 다익스트라는 일반적인 형태와 똑같이 구현. 다만 매개변수에 배열을 넣어서 해당 배열을 채워 주는 구조로 

 

2. dist배열을 s에서 시작할 때, g에서 시작할 때, h에서 시작할 때 총 3개를 만들고 다익스트라 함수도 총 3번 호출

 

3.  min( s-g-h-목표 지점, s-h-g-목표지점)이  s-목표지점과 같은지 확인  

 

 

 

 

정답 코드

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

int T, n, m, t, s, g, h;
int a, b, d, temp;

vector <int> destin; //목적지 위치, 시작점에서 다이렉트로 도달할 때 거리를 저장할거
int dist_s[2001];
int dist_g[2001];
int dist_h[2001];
vector <pair<int,int>> arr[2001];

void dijkstra(int start, int dist[2001]) {
	priority_queue <pair<int,int>> que;
	que.push(make_pair(0, start));
	dist[start] = 0;

	while (!que.empty()) {
		int cost = que.top().first *  -1;
		int cur = que.top().second;
		que.pop();


		for (int i = 0; i < arr[cur].size(); i++) {
			int before_v = dist[arr[cur][i].first];
			int current_v = cost + arr[cur][i].second;
			if (before_v > current_v) {
				dist[arr[cur][i].first] = current_v;
				que.push(make_pair(current_v*-1, arr[cur][i].first));
			}
		}

	}



}



int main() {
	

	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d", &n, &m, &t);
		scanf("%d %d %d", &s, &g, &h);
		
		
		//초기화 
		destin.clear();
		for (int i = 1; i <= 2000; i++) {
			arr[i].clear();
			dist_s[i] = 2000000000;
			dist_g[i] = 2000000000;
			dist_h[i] = 2000000000;
		}
		
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &a, &b, &d);
			arr[a].push_back(make_pair(b, d));
			arr[b].push_back(make_pair(a, d));
		}

		for (int i = 0; i < t; i++) {
			scanf("%d", &temp);
			destin.push_back(temp);
		}

		sort(destin.begin(), destin.end()); // 오름차순으로 미리 정렬해둠	

		dijkstra(s, dist_s);
		dijkstra(g, dist_g);
		dijkstra(h, dist_h);

		

		for (int i = 0; i < destin.size(); i++) {

			if (dist_s[destin[i]] == (dist_s[g] + dist_g[h] + dist_h[destin[i]]))
				cout << destin[i] << ' ';
			else if(dist_s[destin[i]] == (dist_s[h] + dist_h[g] + dist_g[destin[i]]))
				cout << destin[i] << ' ';
		}
		cout << endl;


		/*
		cout << endl;
		for (int i = 1; i <= n; i++) {
				cout << dist2[i] << ' ';
		}
		cout << endl;
		*/

	}

	return 0;
}