백준 11779번, 최소 비용 구하기2(C, C++)

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

11779번: 최소비용 구하기 2

#include<iostream>
#include<vector>
#include<queue>

#define INF 100000000

using namespace std;

int dist[1001];
int N;
int M;
vector<pair<int, int>> a[100001];
int location[100001];

void dijkstra(int start){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 0; i <= N; i++){
        dist[i] = INF;
    }
    dist[start] = 0;
    pq.push({0, start});
    while(!pq.empty()){
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if(dist[cur] < cost){
            continue;
        }

        for(int i = 0; i < a[cur].size(); i++){
            int ncost = a[cur][i].second + cost;
            int next = a[cur][i].first;
            if(dist[next] > ncost){
                dist[next] = ncost;
                location[next] = cur;
                pq.push({dist[next], next});
            }
        }
    }    
}
int main(){
    int start;
    int end;

    cin>>N;
    cin>>M;
    for(int i = 1; i <= M; i++){
        int x;
        int y;
        int z;
        cin>>x>>y>>z;
        a[x].push_back({y, z});   
    }

    cin>>start>>end;
    dijkstra(start);
    cout<<dist[end]<<'\n';

    int idx = end;

    vector<int> s;
    while(idx){
        s.push_back(idx);
        idx = location[idx];
    }

    cout<< s.size() <<'\n';
    for(int i = s.size() - 1; i >= 0; i--){
        cout<<s[i]<<" ";
    }
}

 

일반적인 다익스트라 알고리즘의 문제지만,

경로를 저장하는 것과 지나온 경로에 대한 카운트를 어떻게 셀 지 고민했습니다.

예를 들어 1 - > 3 - > 5 정점의 경로를 지난다고 해봅시다.

location[5] = 3, location[3] = 1는 해당 배열의 인덱스에 대한 값은 그 이전 노드의 인덱스입니다.

 

따라서 idx를 vector에 넣어주고 , 그 인덱스를 넣은 배열의 값은 이전 노드의 인덱스 값이므로 새롭게 갱신해줍니다.

이에 대한 코드를 구현하여 while문을 통해 idx가 1이상이 아니면 while문을 나오도록 해줍니다.

while문을 나오게 되면 vector함수에는 5, 3, 1이 저장되어있습니다.

저희가 원하는 값은 1 3 5 이므로 인덱스가 가장 뒤에서 1씩 줄어들도록 for문을 이용하여 출력합니다.

 

 

 

※경로를 저장하는 방법, 배열을 이용해 현재 노드의 인덱스로 이전 노드에 인덱스를 표시할 수 있다는 것을 배움.