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

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

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

다익스트라를 사용하여 푸는 문제였습니다.

기존 다익스트라 문제와 다른점은 최단 경로를 출력하는게 다른 점이었는데요. 저같은 경우 다익스트라의

dist배열을 갱신할때 같이 현재까지의 최단 경로를 기록한 route배열을 같이 갱신하여 풀었습니다. 

route[시작] = route[목적지]  route[목적지].push_back(목적지) 이런식으로 갱신했습니다.

#include <stdio.h>
#include<queue>
#include<iostream>
#include<vector>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int N,M;
int main() {
    fast_io();
    int T;
    cin>>T;
    for(int test=1;test<=T;test++){
        cin>>N>>M;
        vector<vector<int>> route(M+1,vector<int>());
        vector<vector<pair<int,int>>> E(M+1,vector<pair<int,int>>());
        vector<int> dist(M+1,1e9);
        priority_queue<pair<int,int>> pq;
        for(int x=0;x<N;x++){
            int src,dst,cost;
            cin>>src>>dst>>cost;
            E[src].push_back({dst,cost});
            E[dst].push_back({src,cost});
        }        
        pq.push({0,0});
        route[0].push_back(0);
        while(!pq.empty()){
            int now=pq.top().second;
            int cost=-pq.top().first;
            pq.pop();
            if(dist[now]<cost) continue;
            for(auto i : E[now]){
                if(i.second+cost<dist[i.first]){
                    dist[i.first]=i.second+cost;
                    route[i.first]=route[now];
                    route[i.first].push_back(i.first);
                    pq.push({-dist[i.first],i.first});
                }
            } 
        }
        cout<<"Case #"<<test<<": ";
        for(auto i : route[M-1]){
            cout<<i<<" ";
        }
        if(route[M-1].empty()) cout<<-1;
        cout<<'\n';
    }
}