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

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
const int INF = 987654321;
int T, n, m, t, s, g, h, a, b, d, x;
vector<pair<int, int>> adj[2003];
vector<int> wh, res;
int distS[2003], distG[2003], distH[2003]; // s, g, h에서 각각의 최단 거리

void INPUT() {
    cin >> n >> m >> t;
    cin >> s >> g >> h;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> d;
        adj[a].push_back({b, d});
        adj[b].push_back({a, d});
    }
    for (int i = 0; i < t; i++) {
        cin >> x;
        wh.push_back(x);
    }
}

void CLEAR() {
    for (int i = 0; i < 2003; i++) {
        adj[i].clear();
    }
    wh.clear();
    res.clear();
}

void dijkstra(int start, int dist[]) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    fill(dist, dist + 2003, INF);
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int d = pq.top().first;
        int here = pq.top().second;
        pq.pop();
        
        if (dist[here] < d) continue;
        
        for (auto& pa : adj[here]) {
            int nxt = pa.first;
            int nextDist = d + pa.second;
            if (dist[nxt] > nextDist) {
                dist[nxt] = nextDist;
                pq.push({nextDist, nxt});
            }
        }
    }
}

void SOLVE() {
    // s, g, h에서의 최단 경로를 각각 계산
    dijkstra(s, distS);
    dijkstra(g, distG);
    dijkstra(h, distH);
    
    int gToH = distG[h]; // g와 h 사이의 거리

    for (int i = 0; i < t; i++) {
        int target = wh[i];
        // 두 경로: s -> g -> h -> target 또는 s -> h -> g -> target
        int sToTargetViaGH = distS[g] + gToH + distH[target];
        int sToTargetViaHG = distS[h] + gToH + distG[target];

        // 목표 노드로 가는 최단 경로가 s->g->h 또는 s->h->g 경로를 포함할 때
        if (distS[target] == sToTargetViaGH || distS[target] == sToTargetViaHG) {
            res.push_back(target);
        }
    }

    sort(res.begin(), res.end());
    for (int i : res) cout << i << " ";
    cout << '\n';
}

void FASTIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main() {
    FASTIO();
    cin >> T;
    while (T--) {
        CLEAR();
        INPUT();
        SOLVE();
    }
    return 0;
}

풀이

s에서 출발해서 g,h를 거쳐 후보지점을 거치는지 확인하면 된다. 이를 위해 s를 출발지점으로 하는 최단거리, g를 출발지점으로 하는 최단거리, h를 출발지점으로 하는 최단거리를 구한다. 그리고 s - g - h - 후보지점 또는 s - h - g - 후보지점을 탐색한다. 만약 s에서의 비용이 s - g - h - target 또는 s - h- g - target과 같으면 목적지라고 할 수 있다.

 

특정한 최단 거리 문제랑 접근이 비슷하다고 느꼈다.