[백준/BOJ] 1916 최소비용 구하기

문제 : 1916 최소비용 구하기

1916번: 최소비용 구하기

 

도시의 개수와 도시들 간에 운행하는 버스의 비용이 주어졌을 때

최소비용으로 이동하는 금액을 출력하는 문제이다.

다익스트라 알고리즘을 이용해서 해결하면 최소비용을 쉽게 구할 수 있다.

---

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e9+7
using namespace std;
struct ABC{
    ll idx, dst;
    ABC() {}
    ABC(ll idx, ll dst): idx(idx), dst(dst) {} 
};
bool operator<(ABC x, ABC y){
    return x.dst>y.dst;
}
ll N, M, visited[1005];
vector<ABC> arr[1005];
priority_queue<ABC> pq;
ll dijkstra(ll st, ll ed){
    fill(&visited[0],&visited[1004],INF);
    visited[st]=0;
    pq.push({st,0});
    while (!pq.empty()){
        ll x=pq.top().idx, curr=pq.top().dst;
        pq.pop();
        if (curr>visited[x])
            continue;
        for (int i=0;i<arr[x].size();i++){
            ll dx=arr[x][i].idx, next=arr[x][i].dst;
            if (visited[dx]>curr+next){
                visited[dx]=curr+next;
                pq.push({dx,curr+next});
            }
        }
    }
    return visited[ed];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=0;i<M;i++){
        ll a, b, c;
        cin >> a >> b >> c;
        arr[a].push_back({b,c});
    }
    ll st, ed;
    cin >> st >> ed;
    cout << dijkstra(st,ed);
    return 0;
}