[c++] 백준 11779 - 최소비용 구하기 2(DP, 그래프)

0. [c++] 백준

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

1. 풀이

2. 소스코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
 
using namespace std;
 
const int INF = 1000000007;
int N, M;
int trace[1001];
vector<pair<int, int> > V[1001];
 
void dijkstra(const int& start, const int& end) {    
    vector<int> dist(N + 1, INF);
    dist[start] = 0;
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });
 
    while (!pq.empty()) {
        int cost = pq.top().first;
        int here = pq.top().second;
        pq.pop();
 
        if (dist[here] < cost)
            continue;
 
        for (int i = 0; i < V[here].size(); i++) {
            int there = V[here][i].first;
            int next_cost = cost + V[here][i].second;
 
            if (dist[there] > next_cost) {
                dist[there] = next_cost;
                trace[there] = here;
                pq.push({ next_cost, there });
            }
        }
    }
    cout << dist[end] << endl;
}
 
void find_route(const int& start, const int& end) {
    vector<int> ans;
    ans.push_back(end);
    int there = end;
    while (there != start) {
        there = trace[there];
        ans.push_back(there);
    }
    cout << ans.size() << endl;
    reverse(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N >> M;
 
    int a, b, c;
 
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        V[a].push_back({ b,c });
    }
 
    int start, end;
    cin >> start >> end;
 
    dijkstra(start, end);
 
    find_route(start, end);
 
    return 0;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!