이번 문제는 전에 사용했던 다익스트라 알고리즘을 활용하여 푸는 문제였다.
Dijkstra (다익스트라)

• 우선순위 큐에 넣기 때문에 작은 값들의 우선순위가 default로 높게 잡힌다. 그러므로 -를 해서 우선순위 큐에 넣어줘야 한다.

Code

#include <iostream>
#include <queue>
#include <vector>
#define MAX 1001
#define BMAX 100001
#define INF 987654321
using namespace std;

int n, m;
vector<pair<int, int>> Bus[MAX];
int start, destination;
int dist[MAX];

void Input(){
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int a,b,c;
        cin>>a>>b>>c;
        Bus[a].push_back(make_pair(b,c));
    }
    cin>>start>>destination;
    for(int i=1; i<=n; i++){
        dist[i]=INF;
    }
}

void Dijkstra(){
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));
    dist[start]=0;
    while(!pq.empty()){
        int cost=-pq.top().first;
        int cur=pq.top().second;
        pq.pop();
        if(dist[cur]<cost)
            continue;
        for(int i=0; i<Bus[cur].size(); i++){
            int next=Bus[cur][i].first;
            int ncost=cost+Bus[cur][i].second;
            if(dist[next]>ncost){
                dist[next]=ncost;
                pq.push(make_pair(-ncost, next));
            }
        }
    }
    cout<<dist[destination]<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Dijkstra();
    return 0;
}