최소비용 구하기 2 - 11779

//11779 - 최소비용 구하기2
 
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
 
#define INF 1000000000
 
int N, M;
vector<vector<pair<int, int>>> adj;
int S, E;
 
void init()
{
    cin >> N >> M;
    adj = vector<vector<pair<int, int>>>(N+1);
    int x, y, r;
    for(int i = 0; i<M; ++i)
    {
        cin >> x >> y >> r;
        adj[x].push_back(make_pair(y, r));
    }
    cin >> S >> E;
}
 
void dijkstra(int start)
{
    vector<int> dist(N+1, INF);
    vector<int> parent(N+1);
    dist[start] = 0;
    parent[start] = start;
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));
 
    while(!pq.empty())
    {
        int here = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
 
        if(here != start && dist[here] < cost) continue;
 
        for(int i = 0; i<adj[here].size(); ++i)
        {
            int there = adj[here][i].first;
            int c = adj[here][i].second;
            if(dist[there] > cost + c)
            {
                dist[there] = cost + c;
                parent[there] = here;
                pq.push(make_pair(-(cost+c), there));
            }
        }
    }
 
    cout << dist[E] << "\n";
    stack<int> s;
    for(int i = E; i != parent[i]; i = parent[i])
        s.push(i);
    s.push(S);
    cout << s.size() << "\n";
    while(!s.empty())
        cout << s.top() << " ", s.pop();
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    dijkstra(S);
}

 

 

 

 

 

 

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

11779번: 최소비용 구하기 2

 

 

 

 

 

 

최소비용 구하기 2

최단경로 비용과 그 경로를 출력하는 다익스트라 문제입니다.