(11779) 최소비용 구하기

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

단계별로 풀어보기

32단계(동적 계획법과 최단거리 역추적) 8번째

 

 

 

다익스트라 알고리즘에서 역추적을 해야 하는 문제. DP에서 한 것처럼 값을 갱신할 때마다 이전 정점을 저장하는 from배열을 만들어주면 된다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;
#define INF 100000001
typedef pair<int,int> p;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, a, b;
  
  cin >> n >> m;
  
  priority_queue<p, vector<p>, greater<p>> pq;
  vector adj(n+1, vector<p>());
  vector<int> dist(n+1, INF), from(n+1);
  
  while(m--){
    int u, v, w;
    
    cin >> u >> v >> w;
    
    adj[u].push_back({w, v});
  }
  
  cin >> a >> b;
  
  dist[a]= 0;
  pq.push({0, a});
  
  while(!pq.empty()){
    p now= pq.top();
    pq.pop();

    if(now.second==b)  break;
    if(now.first>dist[now.second])  continue;
    
    for(p next:adj[now.second]){
      if(now.first+next.first<dist[next.second]){
        dist[next.second]= now.first+next.first;
        from[next.second]= now.second;
        pq.push({now.first+next.first, next.second});
      }
    }
  }
  
  cout << dist[b] << "\n";
  
  int x= b;
  vector<int> res;
  
  while(x){
    res.push_back(x);
    x= from[x];
  }
  
  cout << res.size() << "\n";
  
  for(int i=res.size()-1;i>=0;i--)  cout << res[i] << " ";
  
  return 0;
}