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

11779번: 최소비용 구하기 2

---

풀이

다익스트라로 길을 저장하면서 풀면 된다.

 

 

 

코드

#include <bits/stdc++.h>

using namespace std;

vector<pair<int,int>> adj[1001];

int n,e;
int nstart,nend;

void Dijkstra(int src){
    vector<int> dist(1001, 100000002);
    dist[src] = 0;
    int path[1001];
    priority_queue<pair<int,int>> q;
    q.push(make_pair(0,src));
    while(!q.empty()){
        int cost = -q.top().first;
        int node = q.top().second;
        q.pop();
        
        if(dist[node] < cost)
        continue;
        
        int nextCost, nextNode;
        for(int i = 0; i < adj[node].size(); i++){
           // cout << cost << " " << adj[node][i].second << endl;
            nextCost = adj[node][i].second + cost;
            nextNode = adj[node][i].first;
            if(nextCost < dist[nextNode]){
                dist[nextNode] = nextCost;
                path[nextNode] = node;
                q.push(make_pair(-nextCost,nextNode));
            }
        }
    }
    cout << dist[nend] << endl;
    vector<int> vpath;
    int nextNode = nend;
    while(true){
        if(nextNode == nstart){
            break;
        }
        vpath.push_back(nextNode);
        nextNode = path[nextNode];
    }
    cout << vpath.size()+1 << endl;
    cout << nstart << " ";
    for(int i = vpath.size() -1; i >= 0; i--){
        cout << vpath[i] << " ";
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> e;
    int b,nb,c;
    for(int i =0 ; i < e; i++){
        cin >> b >> nb >> c;
        adj[b].push_back(make_pair(nb,c));
    }
    cin >> nstart >> nend;
    Dijkstra(nstart);
    return 0;
}