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

🧨 백준 9370번 - 미확인 도착지

문제 난이도 : 골드2 (어렵다 어려워)

문제 링크 : www.acmicpc.net/problem/9370

9370번: 미확인 도착지

🧨 알고리즘 선택 및 C++ 코드

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

using namespace std;

struct edge { int to, length; };

int dijkstra(const vector<vector<edge>>& graph, int source, int target) {
    vector<int> min_distance(graph.size(), INT_MAX);
    min_distance[source] = 0;
    set<pair<int, int>> active_vertices;
    active_vertices.insert(make_pair(0, source));
    while (!active_vertices.empty()) {
        int where = active_vertices.begin()->second;
        if (where == target)
            return min_distance[where];
        active_vertices.erase(active_vertices.begin());
        for (auto ed : graph[where]) {
            if (min_distance[ed.to] > min_distance[where] + ed.length) {
                active_vertices.erase(make_pair(min_distance[ed.to], ed.to));
                min_distance[ed.to] = min_distance[where] + ed.length;
                active_vertices.insert(make_pair(min_distance[ed.to], ed.to));
            }
        }
    }
    return INT_MAX;
}

int main()
{
    int test;
    cin >> test;
    for (int c = 0; c < test; c++) {
        vector<vector<edge>> graph(50000);
        vector<int> targets;
        vector<int> results;
        int n, m, t;
        cin >> n >> m >> t;
        int s, g, h;
        cin >> s >> g >> h;
        int crosslength = 0;
        for (int i = 0; i < m; i++) {
            int a, b, d;
            cin >> a >> b >> d;
            graph[a].push_back({ b, d });
            graph[b].push_back({ a, d });
            if ((a == g && b == h) || (a == h && b == g)) { 
                crosslength = d; 
            }
        }
        for (int i = 0; i < t; i++) {
            int x;
            cin >> x;
            targets.push_back(x);
        }
        for (auto t : targets) {
            int result = dijkstra(graph, s, t);
            int cross = 0;
            if (s == g) { // s == g != h
                if(h != t) cross = dijkstra(graph, h, t);
                cross += crosslength;
                if (cross <= result && result != INT_MAX) results.push_back(t);
            } 
            else if (s == h) { // s == h != g
                if (g != t) cross = dijkstra(graph, g, t);
                cross += crosslength;
                if (cross <= result && result != INT_MAX) results.push_back(t);
            }
            else { // s != g != h
                int cross1 = dijkstra(graph, s, g);
                cross1 += crosslength;
                if (h != t) cross1 += dijkstra(graph, h, t);

                int cross2 = dijkstra(graph, s, h);
                cross2 += crosslength;
                if (h != t) cross2 += dijkstra(graph, g, t);
                if (min(cross1, cross2) == result && result != INT_MAX) results.push_back(t);
            }
        }
        sort(begin(results), end(results));
        for (auto r : results) {
            cout << r << " ";
        }
        cout << "\n";
    }

    return 0;
}