백준 117799번 최소비용구하기 2

최단거리 역추적 문제

#include<vector>
#include <iostream>
#include<queue>
#include<tuple>

using namespace std;

typedef pair<int,int> ci; 

priority_queue<ci,vector<ci>,greater<ci>>pq; 

int main()
{
   int n,m; 
   cin>>n>>m; 
   vector<vector<ci>>arr(n+1,vector<ci>());
   vector<int>dist(n+1,100000000);
   vector<int>way(n+1,-1);
   int a,b,c;
   for(int i=0;i<m;i++){
       cin>>a>>b>>c; 
       arr[a].push_back({b,c});
   }
   int f,e;
   cin>>f>>e; 
   pq.push({0,f});
   while(!pq.empty()){
       
       int w=pq.top().first; 
       int cur=pq.top().second;
       
       pq.pop(); 
       if(w>dist[cur])continue;
       
       for(int i=0;i<arr[cur].size();i++){
           int nw=arr[cur][i].second; 
           int nx=arr[cur][i].first;
           
           if((w+nw)<dist[nx]){
               dist[nx]=w+nw;
               way[nx]=cur; 
               pq.push({dist[nx],nx});
           }
       }
   }
   
   cout<<dist[e]<<'\n';
   
   vector<int>ans; 
   
   int cnt=0;
   
   ans.push_back(e);
   int x=way[e];
   while(x!=f){
       cnt++; 
       ans.push_back(x);
       x=way[x];
   }
   ans.push_back(f);
   
   cout<<ans.size()<<'\n';
   
   for(int i=ans.size()-1;i>=0;i--){
       cout<<ans[i]<<' ';
   }
   
    return 0;
}