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

백준1916링크

입력

도시의 개수 N(1 ≤ N ≤ 1,000)
버스의 개수 M(1 ≤ M ≤ 100,000)
출발 도시 번호 / 도착 도시 번호 / 비용(1 ≤ 비용 ≤ 100,000)
출발지 / 도착지

출력

출발 도시에서 도착 도시까지 가는데 드는 최소 비용

풀이

다익스트라

• 하나의 출발점 고정
• 음수 간선 X
• 최소 비용 구하기

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define INF 1e9 //무한대
#define MAXN 1001 //최대 노드 수
using namespace std;

int N,M,start,arrival;
vector<pair< int,int>> g[MAXN]; //그래프
long long cost[MAXN]; //출발점에서 각 노드까지의 최소비용 저장

void dijkstra(int s){
    priority_queue<pair< long long , int>> pq;
    pq.push({0,s}); //출발점 큐에 넣기
    cost[s]=0;
    
    while(!pq.empty()){
        long long c=pq.top().first;
        int n=pq.top().second;
        pq.pop();
        
        if(cost[n] < c) continue; //이미 처리된 노드의 경우 무시
        
        for(int i=0;i < g[n].size();i++){
            long long ncost=c+g[n][i].second; //비용 계산
            
            if(ncost < cost[g[n][i].first]){ //경유된 경우의 비용이 적은 경우
                cost[g[n][i].first]=ncost;
                pq.push(make_pair(ncost,g[n][i].first));
            }
        }
    }
    return;
}

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>N;
    cin>>M;
    
    int a,b,c;
    for(int i=0;i < M;i++){
        cin>>a>>b>>c;
        g[a].push_back(make_pair(b, c));
    }
    
    cin>>start>>arrival;
    
    fill(cost,cost+N+1,INF); //cost 배열 무한대로 채우기
    
    dijkstra(start);
    
    cout<<cost[arrival]<<"\n";
    return 0;
}