190305 BOJ 9370번 미확인 도착지

 

다익스트라

 

- 경유지가 목적지 후보가 되는 경우를 처리해줘야 하는데 이걸 알아채는데 시간이 걸렸다...

- http://2013.bapc.eu/ 에서 테스트케이스를 참고할 수 있다.

 

 

풀이

 

1. 주어진 정보대로 다익스트라를 수행한다.

2. g, h 중 더 나중에 도착한 곳에서 최단 경로로 탐색한다.

3. 탐색 중 목적지 후보가 최단 경로를 만족하면 따로 표시해둔다. 

4. 표시해둔 목적지 후보를 출력한다.

 

 

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define endl '\n'
#define ll long long
#define mp(a,b) make_pair(a,b)
#define sws ios::sync_with_stdio(false), cin.tie(NULL);
#define MAX 200000000
#define pii pair<int, int>
using namespace std;
int T, n, m, t, s, g, h, a, b, d, x;
int D[2001], E[2001], target[2001];
 
int main() {
    sws;
    cin >> T;
    while (T--) {
        vector<pii> edge[2001];
        cin >> n >> m >> t;
        cin >> s >> g >> h;
        FOR(i, 1, n + 1) D[i] = E[i] = -1, target[i] = 0;
        FOR(i, 0, m) {
            cin >> a >> b >> d;
            edge[a].push_back(mp(b, d));
            edge[b].push_back(mp(a, d));
        }
        FOR(i, 0, t) {
            cin >> x;
            target[x] = 1;
        }
        priority_queue<pii> q;
        q.push(mp(0, s));
        while (!q.empty()) {
            int cost = -q.top().first;
            int now = q.top().second;
            q.pop();
            if (D[now] != -1) continue;
            D[now] = cost;
            for (pii next : edge[now]) {
                if (D[next.first] != -1) continue;
                q.push(mp(-cost - next.second, next.first));
            }
        }
        int b = D[g] < D[h] ? h : g;
        q.push({ 0,b });
        while (!q.empty()) {
            int cost = -q.top().first;
            int now = q.top().second;
            q.pop();
            if (E[now] != -1) continue;
            E[now] = cost;
            for (pii next : edge[now]) {
                if (E[next.first] != -1) continue;
                q.push(mp(-cost - next.second, next.first));
            }
        }
 
        FOR(i, 1, n + 1) 
            if (target[i] != 0 && D[i] != -1 && E[i] != -1 && D[i] == D[b] + E[i]) cout << i << ' ';
        
        cout << endl;
    }
}