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

11779번: 최소비용 구하기 2

다익스트라를 이용하는 문제이다. 간단한 다익스트라 구현 문제이다. 여기서 추가된 점은 최소비용을 가지는 노드들을 출력해야 한다는 점이다. 이부분은 다익스트라 과정에서 이전의 인덱스를 저장하여 해결하였다. index 배열은 이전의 위치를 저장하는 배열이다. 다익스트라 과정에서 기존 비용보다 더 낮은 비용을 가지는 길을 찾았을 때 다음의 위치에 해당하는 인덱스에 현재 위치를 저장해주었다. 과정이 끝나고 반복문을 통해 이전 위치의 인덱스를 찾아가면서 벡터에 저장해주고 벡터의 크기와 백터 값들을 출력해주었다.
다익스트라를 구현하는 것은 금방 할 수 있었지만 노드들을 출력하는 과정이 오래 걸렸다. 아이디어를 떠올리기 쉽지 않았다. 더 많은 문제를 풀어봐야 겠다.

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

using namespace std;

int n, m, s, e;
vector<pair<int, int>> v[1001];
vector<int> res;
int index[1001];
int d[1001];

void dijkstra() {
    priority_queue<pair<int, int>> pq;

    d[s] = 0;
    pq.push({ s,0 });

    while (!pq.empty()) {
        int cur = pq.top().first;
        int cost = -pq.top().second;

        pq.pop();

        if (d[cur] < cost) continue;

        for (int i = 0; i < v[cur].size(); i++) {
            int next = v[cur][i].first;
            int nd = cost + v[cur][i].second;

            if (d[next] > nd) {
                d[next] = nd;
                index[next] = cur;
                pq.push({ next, -nd });
            }
        }
    }
}

void solution() {
    for (int i = 1; i <= 1001; i++) {
        d[i] = 2000000000;
    }

    dijkstra();

    int i = index[e];

    res.push_back(e);
    while (i) {
        res.push_back(i);
        i = index[i];
    }

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
    }

    cin >> s >> e;

    solution();

    return 0;
}