[다익스트라] BOJ 9694 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (C++)

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

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

 

문제 해결 알고리즘

 

최고의원을 만나기까지 친밀도의 합 중 가장 작은 값을 구하는 것이 아니라 거기까지의 최단 경로를 추적하는 문제여서 약간 까다로울 수도 있었던 문제였다. 

 

다익스트라 알고리즘에서 더 값이 적은 경로가 나왔을 때, 해당 위치가 어떤 위치에서 왔는지 기록하는 배열을 만들어서 추적했다. 

 

아래의 링크에 다익스트라 알고리즘에대한 설명이 있다.

https://kimmessi.tistory.com/185?category=871925 

[알고리즘] 다익스트라 - 선형 탐색, 우선순위 큐

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;
int N, M;

int d[21], route[21];
vector<pair<int, int>> graph[21];

void dijkstra(){

    priority_queue<pair<int ,int>> pq;

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

    route[0] = -1;

    while(!pq.empty()){
        
        int dist = -pq.top().first;
        int now = pq.top().second;

        pq.pop();

        if(d[now] < dist) continue;

        for(int i=0;i<graph[now].size();i++){
            int cost = dist + graph[now][i].second;

            if(cost < d[graph[now][i].first]){

                route[graph[now][i].first] = now;
                d[graph[now][i].first] = cost;
                pq.push({-cost, graph[now][i].first});
            }
        }
    }
}

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

    for(int i=1;i<=T;i++){

        stack<int> result;
        cin >> N >> M;

        for(int j=0;j<N;j++){
            int x, y, z;
            cin >> x >> y >> z;

            graph[x].push_back({y, z});
            graph[y].push_back({x, z});
        }

        fill(d, d+20, INF);
        fill(route, route+20, -9);

        dijkstra();

        cout << "Case #" << i << ": ";

        if(route[M-1] == -9) cout << -1 << '\n';
        else{
            int pos = M-1;
            while(pos != 0){    
                result.push(pos);
                pos = route[pos];
            }

            result.push(0);

            while(!result.empty()) {
                cout << result.top() << ' ';
                result.pop();
            }
            cout << '\n';
        }

        for(int i=0;i<21;i++) graph[i].clear();

    }
}