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

문제 :

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

분석 :

이 문제 역시 대표적인 다익스트라 알고리즘 문제이다.

1753번 문제

2021.03.10 - [Algorithm🐰/백준] - [백준] 1753 최단 경로 dijkstra

에 가는 마지막 노드 end 만을 출력하게끔 변형하면 된다.

 

 

c++ 코드 :

//
//  1916_min_cost.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/03/10.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define INF 1e9 //1000000000

vector<pair<int, int>>vertex[1001];
int d[100001]; // 최단 거리 테이블

void min_bus(int start, int end){
    priority_queue<pair<int, int>>pq;
    pq.push(make_pair(0, start));
    d[start] = 0;
    while(!pq.empty()){
        //우선 순위 큐는 가장 큰 원소 top으로 놓으므로
        //거리 작은 정점부터 꺼내지도록 하기
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        if(d[now] < dist) { continue; }
        for(int i = 0; i < vertex[now].size(); i++){
            int cost = dist + vertex[now][i].second;
            
            if(cost <d[vertex[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            {
                d[vertex[now][i].first] = cost;
                pq.push(make_pair(-cost,vertex[now][i].first));
            }
        }
    }
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int city;
    cin >> city;
    int bus;
    cin >> bus;
    for(int i = 0 ; i < bus; i++){
        int in, to, cost;
        cin >> in >> to >> cost;
        vertex[in].push_back({to, cost});
    }
    
    int start, end;
    cin >> start >> end;
    fill(d, d+100001, INF);
    min_bus(start, end);
    cout << d[end] << '\n';
    
    
    return 0;
}