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

문제 링크

9370번: 미확인 도착지

 

풀이

문제가 복잡해보이지만 1504번 풀었다면 그렇게 어렵지 않은 문제
최단 경로에서 특정한 노드를 지나는 최단 경로를 구하는 문제이다.

1. 값을 입력받으며 인접 리스트를 만든다.
2. 루트 3개를 비교할텐데 s -> g -> h -> 후보지, s -> h -> g -> 후보지 중 작은 값과, s -> 후보지 값을 비교해서 같다면 해당 경로를 지났단 뜻이므로 answer에 추가해준다.
3. 루트를 지나는 경로의 길이를 구할 때는 다익스트라 알고리즘을 사용한다.
   1. 출발 노드에서 모든 노드까지의 거리는 무한대로 만든뒤, 자신의 노드 dist만 0으로 만들어준다.
   2. 우선순위 큐를 이용하여 거리가 작은 노드부터 순서대로 방문한다.
   3. 해당 노드를 방문할 때 거리가 최소로 갱신된다면 pq에 넣고 dist를 갱신해준다.
   4. func 함수에서는 해당 노드에서 모든 노드까지의 최소 거리가 담긴 dist를 return한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 100000001
using namespace std;

vector<int> func(int u, int n, vector<vector<pair<int,int>>> &adj)
{
    vector<int> dist(n + 1, INF);
    priority_queue<pair<int, int>> pq;

    dist[u] = 0;
    pq.push({ 0, u });

    while (!pq.empty())
    {
        int cur = pq.top().second;
        pq.pop();
        for (int i = 0; i < adj[cur].size(); i++)
        {
            int next = adj[cur][i].second;
            int cost = adj[cur][i].first;
            if (dist[next] > dist[cur] + cost)
            {
                dist[next] = dist[cur] + cost;
                pq.push({ cost, next });
            }
        }
    }

    return dist;
}

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

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

        vector<vector<pair<int,int>>> adj(n + 1);
        for (int i = 0; i < m; i++) // 인접 리스트 만들기
        {
            int a, b, d;
            cin >> a >> b >> d;
            adj[a].push_back({ d, b });
            adj[b].push_back({ d,a });
        }

        vector<int> startS = func(s, n, adj);
        vector<int> startG = func(g, n, adj);
        vector<int> startH = func(h, n, adj);

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

            int route1 = startS[x]; // 시작 -> 목적지
            int route2 = startS[g] + startG[h] + startH[x]; // 시작 -> g -> h -> 목적지
            int route3 = startS[h] + startH[g] + startG[x]; // 시작 -> h -> g -> 목적지

            if (route1 == min(route2, route3))
            {
                answer.push_back(x);
            }
        }

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