백준 14284 - 간선 이어가기2, C++, 다익스트라

14284번: 간선 이어가기 2

#include <iostream>
#include <queue>
#include <vector>
#include <limits.h>
using namespace std;

int n, m, s, t;
vector<pair<int, int>> edges[5001];
int cost_from_start[5001];

void Djik(){
    priority_queue<pair<int, int>> q;   // cost, vertex
    q.push({0, s});
    cost_from_start[s] = 0;

    while(!q.empty()){
        int cur = q.top().second;
        int cost = -q.top().first;
        q.pop();

        if(cost_from_start[cur] < cost)
            continue;
        
        if(cur == t){
            cout << cost << endl;
            return;
        }
        

        for(unsigned i = 0; i < edges[cur].size(); i++){
            int next_pos = edges[cur][i].first;
            int next_cost = cost + edges[cur][i].second;

            if(next_cost < cost_from_start[next_pos]){
                cost_from_start[next_pos] = next_cost;
                q.push({-next_cost, next_pos});
            }
        }
    }
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input;
    cin >> n >> m;   // vertex, edge count;
    for(unsigned i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;

        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }
    cin >> s >> t;

    // solution
    for(int i = 0; i <= n; i++)
        cost_from_start[i] = INT32_MAX;

    Djik();

    return 0;
    
}

---

평범한 다익스트라 문제였습니다. 다만 시작점과 도착점이 이어지는 순간에 비용이 얼마인지 출력하고 종료하면 되는 문제로 이점만 유의하면 무난하게 풀 수 있습니다.