백준 1916번: 최소비용 구하기

문제

문제 바로가기> 백준 1916번: 최소비용 구하기

풀이

다익스트라 알고리즘을 이용하여 start 정점으로부터 모든 다른 정점까지의 최단 경로를 구할 수 있다. 그 중 end 정점으로의 최단 경로를 출력하면 된다. 시간을 절약하기 위해 이미 방문한 정점은 continue문을 사용해 재방문을 피해주었다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

#define INF 987654321
#define MAX_N 1001
#define MAX_M 100001

int N, M, S, E, dist[MAX_N]{};
struct Data{int end, weight;};
vector<Data> eg[MAX_M];
bool visit[MAX_N]={false};

void dijkstra(){
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, S));
    while (!pq.empty()){
        int nownode = pq.top().second; 
        int distance = pq.top().first*(-1);
        pq.pop(); 
        if(visit[nownode]) continue; // 이미 방문한 경우 재방문 x
        visit[nownode] = true;
        for(int i=0; i<eg[nownode].size(); i++){
            int new_cost = dist[nownode] + eg[nownode][i].weight;
            int before_cost = dist[eg[nownode][i].end];
            if(new_cost<before_cost){
                dist[eg[nownode][i].end] = new_cost;
                pq.push(make_pair(-1*new_cost, eg[nownode][i].end));
            }
        }
    }   
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=0; i<M; i++){
        int s, e, w; cin>>s>>e>>w;
        eg[s].push_back({e, w});
    }
    cin>>S>>E;
    for(int i=0; i<MAX_N; i++) dist[i] = INF;
    dist[S] = 0;
    dijkstra();
    cout << dist[E];
}