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

[Gold II]

 

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

9370번: 미확인 도착지

 

풀이 1

다익스트라 문제.

다익스트라로 목적지 후보까지의 최소 경로 길이(value)를 구하고, 경로를 저장한 후, 저장한 경로가 g-h를 지나는 지 확인했다.

예제는 알맞게 답이 나왔으나, 특정 목적지로 향하는, 최소 길이인 경로가 여러 개 존재한다면, 그 중 g-h를 지나는 경로가 있는 지 확인하지 않고, 하나의 경로에 대해서만 확인하여 오답이 나온 듯 하다.

WA.

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

#define init cin.tie(0)->ios_base::sync_with_stdio(0);
#define INF 1e9
using namespace std;
typedef pair<int, int> pint;

vector<vector<int>> answer;

int main() {
    init;
    int T;
    cin >> T;

    for (int p = 0; p < T; p++) {
        vector<pint> edges[2009];
        priority_queue<pint, vector<pint>, greater<pint>> pq;
        int dist[2009];
        int route[2009];

        int n, m, t;
        cin >> n >> m >> t;
        int s, g, h;
        cin >> s >> g >> h;

        int a, b, d;
        for (int i = 0; i < m; i++) {
            cin >> a >> b >> d;
            edges[a].push_back({d, b});
            edges[b].push_back({d, a});
        }

        int tList[101], x;
        for (int i = 0; i < t; i++) {
            cin >> x;
            tList[i] = x;
        }

        fill(dist, dist + n + 1, INF);
        dist[s] = 0;
        pq.push({0, s});

        while (pq.size()) {
            auto [curd, cur] = pq.top();
            pq.pop();
            if (dist[cur] < curd) continue;
            for (int i = 0; i < edges[cur].size(); i++) {
                auto [nxtd, nxt] = edges[cur][i];
                if (dist[nxt] > curd + nxtd) {
                    dist[nxt] = curd + nxtd;
                    pq.push({dist[nxt], nxt});
                    route[nxt] = cur;  // 경로 저장
                }
            }
        }

        // 경로 추적, 조건 만족 시 저장
        vector<int> result;
        for (int i = 0; i < t; i++) {
            int ptr = tList[i];
            while (ptr != s) {
                if ((route[ptr] == g && ptr == h) || (route[ptr] == h && ptr == g)) {
                    result.push_back(tList[i]);
                }
                ptr = route[ptr];
            }
        }

        sort(result.begin(), result.end());
        answer.push_back(result);
    }

    for (int p = 0; p < T; p++) {
        for (int i = 0; i < answer[p].size(); i++) {
            cout << answer[p][i];
            if (i != answer[p].size() - 1) {
                cout << " ";
            }
        }
        if (p != T - 1) {
            cout << "\n";
        }
    }
}

 

풀이 2

다익스트라로, 가능한 모든 최소 길이인 경로를 탐색할 수는 없으므로, (내가 알기론.. 만약 가능하다면 댓글 남겨 주세요!)

시작점 -> (g 또는 h 중 더 가까운 교차로)의 거리 + g -> h의 거리 + (g 또는 h 중 더 먼 교차로) -> (목적지)의 거리 = 시작점 -> 목적지의 거리 라면, 시작점에서 목적지까지의 최소 거리 경로들 중 하나가 g-h를 지난다는 뜻이므로, 이를 이용해 풀이하였다.

AC.

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

#define init cin.tie(0)->ios_base::sync_with_stdio(0);
#define INF 1e9
using namespace std;
typedef pair<int, int> pint;

vector<vector<int>> answer;

int main() {
    init;
    int T;
    cin >> T;

    for (int p = 0; p < T; p++) {
        vector<pint> edges[2009];
        priority_queue<pint, vector<pint>, greater<pint>> pq;
        int dist[2009];

        int n, m, t;
        cin >> n >> m >> t;
        int s, g, h;
        cin >> s >> g >> h;

        int a, b, d;
        for (int i = 0; i < m; i++) {
            cin >> a >> b >> d;
            edges[a].push_back({d, b});
            edges[b].push_back({d, a});
        }

        int tList[101], x;
        for (int i = 0; i < t; i++) {
            cin >> x;
            tList[i] = x;
        }

        fill(dist, dist + n + 1, INF);
        dist[s] = 0;
        pq.push({0, s});

        while (pq.size()) {
            auto [curd, cur] = pq.top();
            pq.pop();
            if (dist[cur] < curd) continue;
            for (int i = 0; i < edges[cur].size(); i++) {
                auto [nxtd, nxt] = edges[cur][i];
                if (dist[nxt] > curd + nxtd) {
                    dist[nxt] = curd + nxtd;
                    pq.push({dist[nxt], nxt});
                }
            }
        }

        // g, h중 더 가까운 것의 거리를 저장
        int distA;
        int s2;
        if (dist[g] < dist[h]) {
            distA = dist[g];
            s2 = h;
        } else {
            distA = dist[h];
            s2 = g;
        }
        // g - h 사이의 거리
        int distB;
        for (int i = 0; i < edges[g].size(); i++) {
            if (edges[g][i].second == h) {
                distB = edges[g][i].first;
                break;
            }
        }
        // (s2) - (목적지) 의 최단거리
        int distC[2009];
        fill(distC, distC + n + 1, INF);
        distC[s2] = 0;
        pq.push({0, s2});

        while (pq.size()) {
            auto [curd, cur] = pq.top();
            pq.pop();
            if (distC[cur] < curd) continue;
            for (int i = 0; i < edges[cur].size(); i++) {
                auto [nxtd, nxt] = edges[cur][i];
                if (distC[nxt] > curd + nxtd) {
                    distC[nxt] = curd + nxtd;
                    pq.push({distC[nxt], nxt});
                }
            }
        }

        /* s - (g or h) / g - h / s2(g or h) - 목적지 의 세 거리의 합이
        s - 목적지 의 거리와 동일하면 g-h를 지나는 최단 경로가 존재하는 것. */
        vector<int> result;
        for (int i = 0; i < t; i++) {
            int goal = tList[i];
            if (distA + distB + distC[goal] == dist[goal]) {
                result.push_back(tList[i]);
            }
        }

        sort(result.begin(), result.end());
        answer.push_back(result);
    }

    for (int p = 0; p < T; p++) {
        for (int i = 0; i < answer[p].size(); i++) {
            cout << answer[p][i];
            if (i != answer[p].size() - 1) {
                cout << " ";
            }
        }
        if (p != T - 1) {
            cout << "\n";
        }
    }
}