백준11779 - 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

다익스트라를 이용하여 푼 문제이다. 특별한 점은 경로를 출력해야 된다는 것이다. 출발 노드에서 도착점으로 향하는 맵을 최대 도시의 갯수로 구성하여 더 짧은 경로가 들어오면 경로를 바꿔주는 형식으로 문제를 해결하였다.

#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;

int n, m;
int x, y, z;
int a, b;
int d[1001];
vector<pair<int, int>> v[1001];
map<int, vector<int>> mp;

void dijkstra(int start) {
    d[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push(pair<int, int>(start, 0));
    
    while(!pq.empty()) {
        int current = pq.top().first;
        int distance = -pq.top().second;
        pq.pop();
        
        if(d[current] < distance) {
            continue;
        }
        
        for(int i = 0; i < v[current].size(); i++) {
            int next = v[current][i].first;
            int nextDistance = distance + v[current][i].second;
            
            if(nextDistance < d[next]) {
                d[next] = nextDistance;
                mp[next] = mp[current];
                mp[next].push_back(next);
                pq.push(pair<int, int>(next, -nextDistance));
            }
        }
    }
}

int main() {
    cin >> n;
    cin >> m;
    
    for(int i = 1; i <= 1000; i++) {
        d[i] = 987654321;
    }
    
    for(int i = 0; i < m; i++) {
        cin >> x >> y >> z;
        v[x].push_back(pair<int, int>(y, z));
    }
    
    cin >> a >> b;
    
    for(int i = 1; i <= 1000; i++) {
        mp[i].push_back(a);
    }
    
    dijkstra(a);
    
    cout << d[b] << '\n';
    cout << mp[b].size() << '\n';
    for(int x : mp[b]) {
        cout << x << ' ';
    }
    return 0;
}