최소비용 구하기 (feat. 백준, 1916번)

최소비용 구하기
https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    int N, M, X, Y;
    set<pair<int, int>> arr[1001];
    int ans[1001]{0};
    cin >> N >> M;
    for(register int n = 1; n <= N; ++n)
        ans[n] = 99999999;
    for(register int m = 0, x, y, c; m < M; ++m)
        cin >> x >> y >> c, arr[x].insert(make_pair(y, c));
    cin >> X >> Y;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(0, X));
    ans[X] = 0;
    while(!q.empty()){
        auto p = q.top(); q.pop();
        register int c1 = p.first, x = p.second;
        if(x == Y)
            break;
        if(ans[x] < c1)
            continue;
        for(auto iter = arr[x].begin(); iter != arr[x].end(); ++iter){
            register int y = iter->first, c2 = iter->second;
            if(ans[y] > c1 + c2)
                ans[y] = c1 + c2, q.push(make_pair(ans[y], y));
        }
    }
    cout << ans[Y];
    return 0;
}
// *&)*@*

 

다익스트라 알고리즘의 전형적인 문제입니다.

풀이 방식을 이해하거나 안된다면 일부는 외우는 것을 추천 드립니다.

결국 N->M 으로 갈때의 최소 비용을 구하는 방식이고, 이러한 방식은 N->M, N->A->M, N->B->M 등 다양합니다.