백준 11779 - 최소비용 구하기 2

http://icpc.me/11779

 

출발 도시에서 도착 도시까지 최소비용을 구하는 문제이며, 이는 다익스트라 알고리즘을 그대로 적용할 수 있다.

 

하지만 최소비용뿐만 아니라 최소비용이 되기 위한 경로도 출력할 것을 요구하고 있다.

알아야 할 것

최단 경로의 해는 다익스트라 알고리즘을 수행하면서 배열로 저장할 수 있다.

 

우선순위 큐에서 꺼낸 노드 A와 A가 연결된 노드 B가 최적해를 갱신할 때 그 노드를 배열에 저장해주면 된다.

 

이렇게 하면 실제 최단 경로의 역순으로 노드가 구성된다.

구현

최단 경로를 저장하면서 다익스트라 알고리즘을 수행한 후,

 

저장된 최적해를 거꾸로 출력해주면 AC를 받을 수 있다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using graph = vector<vector<pair<int, int>>>;

int backward[1001];
stack<int> res;

ll dijkstra(graph &adj, int start, int goal);

int main() 
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    
    int v, e;
    cin >> v >> e;
    
    graph al(v);
    
    for (int i = 0; i < e; ++i)
    {
        int from, to, weight;
        cin >> from >> to >> weight;
        
        al[from - 1].push_back({weight, to});
    }
    
    int start, dest;
    cin >> start >> dest;
    
    cout << dijkstra(al, start, dest) << '\n';
    
    int cnt = 0;
    int pntr = dest;
    
    while (pntr)
    {
        ++cnt;
        res.push(pntr);
        pntr = backward[pntr]; 
    }
    
    cout << cnt << '\n';
    while (res.size())
    {
        cout << res.top() << " ";
        res.pop();
    }
}

ll dijkstra(graph &adj, int start, int goal)
{
    vector<ll> dist(adj.size(), 1e12);
    dist[start - 1] = 0;
    
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    q.push({0, start});
    
    while (!q.empty())
    {
        auto cur = q.top();
        q.pop();
        
        if (cur.first > dist[cur.second - 1])
            continue;
        
        for (auto item : adj[cur.second - 1])
        {
            ll next_pay = cur.first + item.first;
            
            if (dist[item.second - 1] > next_pay)
            {
                dist[item.second - 1] = next_pay;
                backward[item.second] = cur.second;
                q.push({next_pay, item.second});
            }
        }
    }
    
    return dist[goal - 1];
}