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

문제링크 : https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<pii>graph[1001];
int dist[1001];
int route[1001];
vector<int> routeV;
int N, M, s, e;

void dijkstra()
{
    priority_queue<pii, vector<pii>,greater<pii>>pq; //비용이 적은 것부터 정렬
    pq.push({0, s}); //비용, 시작점
    dist[s] = 0;
    
    while(!pq.empty())
    {
        auto[cost, cur] = pq.top();
        pq.pop();

        if(dist[cur] < cost) continue;

        for(int i=0; i<graph[cur].size(); i++)
        {
            auto [next, ncost] = graph[cur][i]; //다음 위치 및 비용
            if(dist[next] > cost + ncost)
            {
                route[next] = cur; // 경로 저장
                dist[next] = cost + ncost; //비용 저장
                pq.push({ncost + cost, next}); //다음 비용 및 위치 토스
            }

        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;
    for(int i=1; i<=N; i++) dist[i] = MAX;
    for(int i=0; i<M; i++)
    {
        int u, v, weight;
        cin >> u >> v >> weight;
        graph[u].push_back({v, weight});
    }
    cin >> s >> e;
    dijkstra();
    cout << dist[e] << "\n"; //최소 비용
    while(e)
    {
        routeV.push_back(e); //뒤에서부터 경로 저장
        e = route[e]; //이어진 경로 저장
    }
    cout << routeV.size() << "\n";
    for(int i=routeV.size()-1; i>=0; i--)
    {
        cout << routeV[i] << " "; //담아논 경로 출력 (앞에서 부터 출력 (역순))
    }

    return 0;
}

전형적인 다익스트라 문제에서 추가적으로 경로를 저장해줘야 하는 문제이다.

경로 저장용 새로운 배열을 만들고, 비용을 저장해주는 부분에서 다음값과 연결된 현재 경로를 저장해준다.

 

이후 경로를 출력해줄때는 목적지인 end값에서 앞으로 연결된 값을 추적해주면서 해당 경로값들을 따로 저장해준다.

이후 출력할때 앞에서 뒤에서부터 저장했기 때문에 역순으로 하여 앞에서부터 값을 출력해준다.