[백준/C++] 11779번 최소비용 구하기2

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

11779번: 최소비용 구하기 2

일반적인 다익스트라 알고리즘을 적용하면 된다.

"다음 노드로 가는 가중치 + 현재 노드까지의 비용 < 다음 노드가 기존에 가지고 있던 비용" 이라면 다음 노드의 비용을 업데이트해주는 식으로 그래프를 탐색하면 된다.

if(dist[now]!=cost) continue; 
if(dist[now] < cost) continue; // 동일한 코드!

중간에 이런 코드가 보일텐데, 직관적으로 이해하기는 힘들 것이다.

최솟값을 찾기 위함인데, 큐에서 빼낸 값보다 저장된 값이 더 크다면 굳이 탐색할 필요가 없기 때문이다!

(ex. 초기에 주어진 노드 1번에서 5번으로 가는 비용이 10이라고 하자, 근데 우리가 탐색을 하면서 1 - 3 - 5번 노드로 가는 경로의 비용이 4인 것을 알아내었을 때, 큐에 들어가 있는 {5, 10}에 대해 굳이 탐색할 이유가 없다)

그리고 이 문제가 일반 다익스트라와 다른 점은 경로상의 노드를 출력해야한다는 점인데, 이는 배열을 이용해 해결할 수 있다.

route라는 배열을 두고 최솟값이 갱신되었을 때, route[다음 노드의 번호]에 현재 노드의 번호를 대입한다.

즉, route[next]=now 라는 코드는 최소신장트리가 완성됨에 따라 자동적으로 해당 노드까지 최소 비용으로 갈 수 있도록 하는 직전 노드의 번호를 저장하고 있을 것이다.

(ex. 최소 경로가 1-3-5라고 하자, 그렇다면 route[1]에는 0, route[3]에는 1, route[5]에는 3이 저장되어 있을 것이다!)

역순이므로 스택을 이용해서 값을 저장 및 출력하였다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#include <string>
#include <queue>
#include <functional>
#include <complex>
#include <cmath>
#include <unordered_map>
#include <map>
typedef long long ll;
using namespace std;

int n, m,s,e,c,start_city,end_city;
int dist[1001];
int route[1001];
stack<int> ans;
vector<pair<int,int>> v[1001]; // {도착, 비용}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq; // {도착 도시, 비용}

void dijk(){
    memset(dist,127,sizeof(dist));

    dist[start_city]=0;
    route[1]=0;
    pq.push({start_city,0});

    while(!pq.empty()){
        int now = pq.top().first;
        int cost = pq.top().second;
        pq.pop();

        if(dist[now]!=cost) continue;

        for(int i=0; i<v[now].size();i++){
            int next = v[now][i].first;
            int w = v[now][i].second;

            if(dist[next] > dist[now] + w){
                dist[next]=dist[now]+w;
                route[next]=now; // next로 가기 위해선 now를 거쳐야 함을 저장
                pq.push({next, dist[next]});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for(int i=0; i<m;i++){
        cin >> s >> e >> c;
        v[s].push_back({e,c});
    }
    cin >> start_city >> end_city;

    dijk();
    cout << dist[end_city] << '\n';

    while(end_city!=0){
        ans.push(end_city);
        end_city = route[end_city];
    }
    cout << ans.size() << '\n';

    while(!ans.empty()){
        cout << ans.top() << ' ';
        ans.pop();
    }
}