[백준 11779] 최소비용 구하기 2

전형적인 다익스트라를 돌면서 추가적으로 무엇인가를 기록해야하는 유형이다.

 

다익스트라만으로 우선적으로 최단거리를 도출하고

최단거리를 구성하는 노드까지 구해야한다.

 

이럴때는 다익스트라를 돌면서 조사해봐야하는 새로운 (next, total + cost) 쌍이 나왔을때

dist[next]를 최신화해주고 pq.push를 해줌과 동시에 해당 노드로 오게된 직전 노드를 기록해주면 된다.

 

이러면 parent[A] 는 A로 최단거리로 올 수 있는 경로에 있는 A로 오기 바로 직전 노드가 된다.

 

따라서 최단 경로를 찾을때는 종점부터 parent[A]가 시점이 나올때까지 돌리면 된다.

 

이 문제에서는 여러 최단경로가 있어도 딱 하나만 출력하면 된다고 했기 때문에 int parent[SIZE] 즉, 배열로 해도 되지만,

만약 모든 최단경로를 출력하라고 한다면 vector<vector<int>> parent[SIZE]; 를 통해 한 개의 노드로 최단거리로 올 수 있는 경로에 있는 직전 노드들을 모두 기록할 수 있게 해야한다.

 

위와 같은 문제도 있다.

 

---

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <climits>

#define SIZE 1001

using namespace std;

int N, M, A, B;

int parent[SIZE];
long long dist[SIZE];
vector<vector<pair<int, int>>> graph(SIZE);

void solve()
{
    // 시작 전 초기화
    for (int i = 1; i <= N; i++)
    {
        dist[i] = INT_MAX;
        parent[i] = i;
    }

    // 오름차순
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push(make_pair(0, A));
    dist[A] = 0;
    parent[A] = A;

    while (!pq.empty())
    {
        long long total = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        // pq에 들어가있는 와중에 cur이 최신화가 되어 더이상 조사할 필요가 없으면
        if (dist[cur] < total)
        {
            continue;
        }

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

            // 기존꺼보다 작아 조사할 필요가 있다면
            if (total + cost < dist[next])
            {
                // 직전 노드 최신화
                parent[next] = cur;
                dist[next] = total + cost;
                pq.push(make_pair(total + cost, next));
            }
        }
    }

    int cur = B;
    int cnt = 0;
    stack<int> s;
    while (cur != A)
    {
        s.push(cur);
        cur = parent[cur];
    }
    s.push(A);

    // 도시 갯수 출력
    cout << dist[B] << "\n";
    cout << s.size() << "\n";
    while (!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> M;

    int start, end, cost;
    for (int i = 0; i < M; i++)
    {
        cin >> start >> end >> cost;
        // 단방향 그래프
        graph[start].push_back(make_pair(end, cost));
    }

    cin >> A >> B;

    solve();

    return 0;
}