[백준/BOJ] acmicpc 11799 최소비용 구하기2 C++ (다익스트라)

문제 

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

 

 

 

풀이

cost가 모두 양수이며, A에서 B 정점으로 가는 최소비용을 구하는 문제이므로 다익스트라 알고리즘으로 풀었다.

다른 다익스트라 문제와는 달리, 어떤 정점들을 거쳐 갔는지 루트를 출력해야 했다.

 

 

코드 1

처음엔 priority queue의 top에 접근 할 때마다 출력해봤는데 당연히 틀렸음.

 

 

코드 2

그래서 route를 2차원 벡터로 만들어

route[n] = { n까지 가는데 거쳐간 정점들 } 

이런식으로 저장했다.

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

int n, m, departure, arrival;
vector<pair<int, int>> graph[1001];
int dist[1001];
vector<int> route[1001];

void dijkstra(){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, departure});
    dist[departure] = 0;
    route[departure].push_back(departure); //route 기록

    while (!pq.empty()){
        //auto [cost, curr] = pq.top();
        int curr = pq.top().second;
        int cost = pq.top().first;

        if(curr == arrival) break;
        pq.pop();

        for(long unsigned int i = 0; i< graph[curr].size(); i++){
            int next = graph[curr][i].first;
            int nextCost = graph[curr][i].second;
            if(dist[next] <= cost + nextCost) continue;

            dist[next] = cost + nextCost;
            pq.push({dist[next], next});
            route[next] = route[curr]; //route 기록
            route[next].push_back(next); //route 기록
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i <m; i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from].push_back({to, cost});
    }
    cin >> departure >> arrival;
    fill_n(dist, n+1, INF);

    dijkstra();

    cout << dist[arrival] <<"\n" << route[arrival].size() <<"\n";
    for(int i = 0; i<route[arrival].size() - 1; i++){
        cout << route[arrival][i] <<" ";
    }
    cout << route[arrival][route[arrival].size()-1] <<"\n";
}

 

 

핵심

for(long unsigned int i = 0; i< graph[curr].size(); i++){
    int next = graph[curr][i].first;
    int nextCost = graph[curr][i].second;
    if(dist[next] <= cost + nextCost) continue;

    dist[next] = cost + nextCost;
    pq.push({dist[next], next});
    route[next] = route[curr];
    route[next].push_back(next);
}

이 부분에서 if문을 타고 넘어가지 않으면, 즉 next의 cost가 더 적다면

pq에 푸쉬를 하고, 이때 route역시 새로 갱신해줬다.

if문을 타지 않았다는 것 자체가 현재 보고 있는 next 노드와 nextCost가 최단거리라는 뜻이니까!

 

 

 

 

풀이 흔적