백준, BOJ, 11779번, 최소비용2 : C++ [CPP] ★

다익스트라의 개념이 조금 더 나아간 것이다.

최단거리로 갱신했을 때는 해당 경로가 정해진다는 것을 기록하면 되는 문제다.

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

 

---

 

#맞는 풀이

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

#define MAX 1002
#define INF 987654321

using namespace std;

int st, ed;
int N, M;

int dist[MAX];
vector<pair<int, int>> adj[MAX];
int path[MAX];

void dijkstra() {
    dist[st] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    heap.push({ dist[st], st });

    while (!heap.empty()) {
        auto cur = heap.top();
        heap.pop();
        int distance = cur.first;
        int idx = cur.second;

        if (dist[idx] != distance)continue;

        for (auto next : adj[idx]) {
            int cost = next.first;
            int nidx = next.second;
            if (dist[nidx] > cost + dist[idx]) {
                dist[nidx] = cost + dist[idx];
                heap.push({ dist[nidx], nidx });
                path[nidx] = idx;
            }
        }
    }
}

int main() {
    cin >> N >> M;
    fill(dist, dist + (N + 1), INF);

    for (int i = 0; i <M; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        adj[from].push_back({cost, to});
    }

    cin >> st >> ed;

    dijkstra();

    cout << dist[ed] << '\n';


    vector<int> ans;
    int x = ed;
    while (x != st) {
        ans.push_back(x);
        x = path[x];
    }
    ans.push_back(x);
    reverse(ans.begin(), ans.end());

    cout << ans.size() << '\n';
    for (auto c : ans) {
        cout << c << ' ';
    }


}

 

 

다만 조금 아쉬운 것은..내가 아쉽다.

개념을 이해했지만 응용력이 조금 부족했다.

 

최단거리 갱신 = 해당 노드까지 경로는 정해짐

이다.