백준 11779. 최소비용 구하기 2 (다익스트라)

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

11779번: 최소비용 구하기 2

1. 특징

1) 우선순위큐를 쓰는 다익스트라 알고리즘

2) 현재 정점 이전 정점을 배열에 저장 (코드에서 pre 배열)

 

2. 코드

#include <iostream>
#include <queue>
#include <algorithm> 
using namespace std;

int v, e; 
int st, en;
int d[100002]; // 최단 거리 테이블
int pre[100002];
vector<pair<int, int>> adj[100002]; // 비용, 정점번호
const int INF = 1e9+10;
int main()
{           
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> v >> e;
    fill(d, d+v+1, INF);

    while(e--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(w, v));
    }

    cin >> st >> en;

    //거리가 작은수부터 출력
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    d[st] = 0;

    //우선순위 큐에 {0, 시작점} 추가
    pq.push(make_pair(d[st], st));
    while(!pq.empty())
    {
        auto cur = pq.top(); pq.pop();
        if(d[cur.second]!=cur.first) continue;
        for(auto nxt: adj[cur.second])
        {
            if(d[nxt.second] <= d[cur.second] + nxt.first) continue;
            d[nxt.second] = d[cur.second] + nxt.first;
            pq.push(make_pair(d[nxt.second], nxt.second));
            pre[nxt.second] = cur.second;
        }
    }


    cout << d[en] << '\n';

    int last = en;
    int cnt = 1;
    vector<int> _ans;
    while(true)
    {
        cnt++;
        last = pre[last];
        _ans.push_back(last);
        if(last == st) break;
    }
    
    cout << cnt << endl; 
    reverse(_ans.begin(), _ans.end());
    for (int i = 0; i < _ans.size(); i++)
        cout << _ans[i] << ' ';
    cout << en;

}