문제

9370번: 미확인 도착지

풀이

s 부터 시작해서 목적지 후보로의 최단 거리를 구하는 문제이다. 이때 그 최단 거리 중 입력으로 주어지는 g, h 사이의 도로를 반드시 지나는 목적지 후보들을 출력하는 문제가 된다.

출발지점이 하나 주어지고 그에 대한 최단 거리를 구해야 하므로 다익스트라 알고리즘을 사용했다.
하지만 다익스트라는 해당 노드까지의 경로가 아닌 거리만을 구하는 알고리즘이라 한번에 뚝딱 정답이 나오지 않았다.

g, h사이의 도로를 반드시 지나는 최단 경로라면
출발지점(s) -> ... -> g혹은 h -> h혹은 g -> ... -> 도착지점 이다.
그렇다면 s 부터 hg도로를 지났을 때의 최단거리 + hg도로를 지난 후 도착지점 까지의 최단 거리가 s부터 도착지점까지의 최단거리가 같아야 한다.

만약 어떤 목적지 후보까지의 최단 거리가 hg 도로를 포함하지 않는다면 s 부터 hg도로를 지났을 때의 최단거리 + hg도로를 지난 후 도착지점 까지의 최단 거리가 다익스트라로 구한 목적지 후보까지의 최단거리보다 큰 값을 가지게 될 것이다.

코드

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

#define node second
#define weight first

using namespace std;

int n, m, t;
int s, g, h;
vector<vector<pair<int, int>>> edges;
vector<int> destination;

vector<int> dijkstra(int start)
{
    vector<int> dist(n+1, INT32_MAX);

    priority_queue<pair<int, int>> pq;
    pq.push({0, start});
    dist[start] = 0;

    while(!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();
        
        if (dist[cur.node] < -cur.weight)
            continue;
            
        for (auto e : edges[cur.node])
        {    
            int nextNode = e.node;
            int nextWeight = e.weight + dist[cur.node];    

            if (dist[nextNode] <= nextWeight)
                continue;

            dist[nextNode] = nextWeight;
            pq.push({-nextWeight, nextNode});
        }
    }

    return dist;
}

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

    int testCase;
    cin >> testCase;
    while (testCase--)
    {
        cin >> n >> m >> t;
        cin >> s >> g >> h;
        edges.assign(n+1, vector<pair<int, int>>());
        for (int i=0; i<m; ++i)
        {
            int a, b, dist;
            cin >> a >> b >> dist;
            edges[a].emplace_back(dist, b);
            edges[b].push_back({dist, a});
        }
        for (int i=0; i<t; ++i)
        {
            int d;
            cin >> d;
            destination.push_back(d);
        }
        
        vector<int> init = dijkstra(s);
        vector<int> distG = dijkstra(g);
        vector<int> distH = dijkstra(h);
        
        vector<int> answer;
        int offset = init[g] > init[h] ? init[g] : init[h];
        vector<int> compare = init[g] > init[h] ? distG : distH;
        for (auto d : destination)
        {
            if (init[d] == compare[d] + offset)
                answer.push_back(d);
        }
        
        sort(answer.begin(), answer.end());
        for (auto a : answer)
            cout << a << " ";
        cout << endl;

        destination.clear();
        edges.clear();
    }


    return 0;
}