[백준 11779][다익스트라][C++] 최소비용 구하기2

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

11779번: 최소비용 구하기 2

 

최소비용 구하기 1에서 최소비용의 경로까지 출력하는 문제이다. 다익스트라 알고리즘에서 최소비용을 갱신할 때마다 나에게로 향하는 노드가 무엇인지 저장해준 후 역순으로 출력해주면 된다.

 

위와 같은 그래프에서 우리는 1번 노드에서 4번 노드로 갈 것이다. 

다익스트라 알고리즘을 위 상황에 적용시켰을 때, 각 노드에서 갱신되는 "1번 노드부터의 거리 배열"이다. 문제에서 요구하는 첫 번째 사항인 최단거리가 몇인지는 손쉽게 구할 수 있다.

이제 최단거리의 경로를 알아내야하는데 이는 다익스트라 알고리즘을 살짝 변형해야한다. 사실 배열을 하나 추가해서 경로를 기억하는 것 뿐이기에 변형이라 보기도 어렵다.

 

배열의 인덱스는 노드 번호를 뜻하고 각 인덱스의 데이터는 최단거리에서 그 노드의 이전 노드를 뜻한다. 따라서 다익스트라 알고리즘에서 최단거리가 갱신될 때마다 배열의 값을 바꿔주면 된다.

최단거리 계산이 완료되면 도착 노드, 위 예시에선 5번 노드로부터 역추적해서 경로를 알아낸 후 경로의 길이와 함께 출력해주면 된다.

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define INF 2e9

int n,m,start,arrive,distances[1001],beforenode[1001];
vector<pair<int,int> > graph[1001];

int main(){
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int in1, in2, in3;
        scanf("%d %d %d",&in1,&in2,&in3);
        graph[in1].push_back(make_pair(in2,in3));
    }

    cin>>start>>arrive;

    for(int i=1; i<=n; i++){
        distances[i]=INF;
    }
    distances[start]=0;

    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
    pq.push(make_pair(0,start));

    while(!pq.empty()){
        pair<int,int> p = pq.top();
        int cost = p.first;
        int node = p.second;
        pq.pop();
        if(distances[node]<cost) continue;

        for(pair<int,int> p : graph[node]){
            int near = p.first;
            int nd = p.second+cost;

            if(distances[near]>nd){
                distances[near]=nd;
                beforenode[near]=node;
                pq.push(make_pair(nd,near));
            }
        }
    }

    vector<int> path;
    int nownode = arrive;
    path.push_back(nownode);
    while(nownode != start){
        nownode = beforenode[nownode];
        path.push_back(nownode);
    }
    cout<<distances[arrive]<<'\n'<<path.size()<<'\n';
    for(int i=path.size()-1; i>=0; i--){
        cout<<path[i]<<' ';
    }

}