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

문제

9370번: 미확인 도착지

풀이

다익스트라 문제이다.

 

• 첫 시도에는 s를 시작점으로 다익스트라를 한번 실시하고, 경로를 추적하여 시도하였지만, 메모리 초과가 발생하였다. 그리고 이 방법은 x까지의 최단 경로가 여러 개 존재할 경우, 답이 올바르지 않을 수 있다. 
• s, g, h를 시작점으로 다익스트라를 세번 실시한다. 
• s -> g -> h -> x로 가는 최단 경로의 비용이 s -> x로 가는 최소 경로의 비용과 일치한다면, 해당 최소 경로는 g -> h를 거친다고 볼 수 있다. 
• 마찬가지로, s -> h -> g -> x로 가는 최단 경로의 비용이 s -> x로 가는 최소 경로의 비용과 일치한다면, 해당 최소 경로는 h -> g를 거친다고 볼 수 있다.
• 즉, 중간 경로가 있는 다익스트라 문제이다. 

코드

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

using namespace std;

vector<vector<pair<int, int>>> edges;
vector<vector<int>> dist;

void dijkstra(int start)
{
    dist[start][start] = 0;

    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));

    while (!pq.empty())
    {
        int current_node = pq.top().second;
        int current_dist = (-1) * pq.top().first;
        pq.pop();

        if (dist[start][current_node] < current_dist)
        {
            continue;
        }

        for (auto edge : edges[current_node])
        {
            int next_node = edge.second;
            int next_dist = edge.first + current_dist;
            if (next_dist < dist[start][next_node])
            {
                dist[start][next_node] = next_dist;
                pq.push(make_pair((-1) * next_dist, next_node));
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    while (T--)
    {
        int n, m, t;
        cin >> n >> m >> t;
        int s, g, h;
        cin >> s >> g >> h;

        edges.resize(n + 1);
        dist.resize(n + 1);
        for (int i = 0; i < dist.size(); ++i)
        {
            dist[i].resize(n + 1, INT_MAX);
        }

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

        // s, g, h를 시작점으로 세 번 다익스트라를 실시
        dijkstra(s);
        dijkstra(g);
        dijkstra(h);

        vector<int> answer;
        for (int i = 0; i < t; ++i)
        {
            int x;
            cin >> x;

            // s -> g -> h -> x 로 가는 경로의 비용이 s -> x 로 가는 최소 경로의 비용이 일치한다면 answer에 추가
            if (dist[s][g] + dist[g][h] + dist[h][x] == dist[s][x])
            {
                answer.push_back(x);
            }
            // s -> h -> g -> x 로 가는 경로의 비용이 s -> x 로 가는 최소 경로의 비용이 일치한다면 answer에 추가
            else if (dist[s][h] + dist[h][g] + dist[g][x] == dist[s][x])
            {
                answer.push_back(x);
            }
        }

        sort(answer.begin(), answer.end());
        for (int i = 0; i < answer.size(); ++i)
        {
            cout << answer[i] << " ";
        }
        cout << '\n';

        edges.clear();
        dist.clear();
    }

    return 0;
}