[Gold 3] 11779 최소비용 구하기 2

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

 

다익스트라 알고리즘을 활용하는 문제

입력으로 시작점과 끝점을 알려준다.

따라서 시작점에서 끝점까지의 최소 비용을 구하면 해결할 수 있다.

 

시작점에서 끝점까지의 최소 비용을 구하는 방법은 일반적인 다익스트라 알고리즘을 활용하면 구할 수 있다.

하지만 최소 비용을 갖는 경로를 구해야하기 때문에 route배열을 따로 정의해야한다.

 

다익스트라 알고리즘의 경로는 now로 부터 next를 구하며

dist[next]가 최소일때 다음 경로가 된다.

따라서 dist[next]가 최소 일때 rout[next]에 now를 넣게 된다면

끝점에서부터 시작점 까지의 경로를 저장할 수 있다.

 

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

#define INF 2000000000;

int N, M;
int st, en;
int dist[1001];
int route[1001];
vector<pair<int,int>> graph[1001];
vector<int> answer;

void dijk(){
    // dist 배열 초기화
    for(int i = 0;i<=N;i++)
        dist[i] = INF;
    
    priority_queue<pair<int, int>> pq;

    pq.push({0, st});
    dist[st] = 0;
    
    while(!pq.empty()){
        int cost = -pq.top().first;
        int now = pq.top().second;

        pq.pop();
        if(dist[now] < cost)
            continue;
        for(int i = 0;i<graph[now].size();i++){
            int next = graph[now][i].first;
            int nCost = graph[now][i].second + cost;

            if(nCost < dist[next]){
                route[next] = now;
                dist[next] = nCost;
                pq.push({-nCost, next});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>N>>M;
    int a, b, c;
    for(int i =0;i<M;i++){
        cin>>a>>b>>c;
        graph[a].push_back({b, c});
    }
    cin>>st>>en;

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

    int temp = en;
    while(temp){
        answer.push_back(temp);
        temp = route[temp];
    }
    cout<<answer.size()<<'\n';
    for(int i = answer.size() - 1;i>=0;i--)
        cout<<answer[i]<<' ';
    
}