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

문제

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

---

문제 요약

n개의 도시가 있고, 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다.

 

A번 도시에서 B번 도시까지 드는 최소 버스 비용과 경로를 출력한다.

---

코드

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

using namespace std;

int n, m;

int start_node, end_node;

vector<pair<int, int>> edges[1010];
vector<int> res;

priority_queue<pair<int, int>> pq;

// dist[i] : 출발 도시에서 i번 도시까지 최소 비용
int dist[1010];

// route[i]: 최소 경로 상에서 i번 도시의 직전 도시
int route[1010];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, w;

        cin >> a >> b >> w;
        
        edges[a].push_back(make_pair(b, w));
    }

    cin >> start_node >> end_node;

    for (int i = 1; i <= n; i++) {
        dist[i] = 1e9;
    }

    pq.push(make_pair(-0, start_node));

    while (!pq.empty()) {
        int d = -pq.top().first;
        int x = pq.top().second;
        pq.pop();

        if (x == end_node) break;

        for (int i = 0; i < edges[x].size(); i++) {
            int nx = edges[x][i].first;
            int nd = edges[x][i].second;

            if (dist[nx] > d + nd) {
                dist[nx] = d + nd;
                pq.push(make_pair(-(d + nd), nx));

                // 직전 도시 저장
                route[nx] = x;
            }
        }
    }     

    cout << dist[end_node] << "\n";

    // 최소 경로 역 추적
    int idx = end_node;

    while (idx != start_node) {
        res.push_back(idx);
        idx = route[idx];
    }
    res.push_back(start_node);

    cout << res.size() << "\n";

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

    return 0;
}

---

코드 설명

다익스트라 알고리즘을 통해 문제를 해결한다.

 

이 때, 경로와 함께 출력해야 하기 때문에, dist 배열을 갱신할 때 직전 도시도 함께 저장(갱신)한다.

 

이 후, 포인터를 하나 두어 도착 도시부터 while문으로 역추적하여 경로를 출력한다.