[백준] 14284번: 간선 이어가기2 / C++

✏️ 문제 링크

https://www.acmicpc.net/problem/14284

14284번: 간선 이어가기 2

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

2021.09.15 - [Algorithm 🧠/알고리듬(thm) 공부 🌱] - [백준] 1916: 최소비용 구하기/ 다익스트라 / C++ ⭐

[백준] 1916: 최소비용 구하기/ 다익스트라 / C++ ⭐

위 문제를 이해하면 쉽게 풀 수 있는 문제 😊

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
using pii=pair<int, int>;

#define MAX 5001
#define INF 987654321

vector<int> dist(MAX, INF);
vector<pii> vec[MAX];

int dijkstra(int s, int t){
    priority_queue<pii> pq; pq.push({0, s});
    dist[s]=0;
    
    while(!pq.empty()){
        pii t=pq.top(); pq.pop();
        int c=t.second; int d=t.first*-1;
        
        if(dist[c]<d)continue;
        for(int i=0; i<vec[c].size(); i++){
            int nxt=vec[c][i].first;
            int nxt_d=vec[c][i].second + d;
            if(nxt_d<dist[nxt]){
                dist[nxt]=nxt_d;
                pq.push({nxt_d*-1, nxt});
            }
        }
    }
    
    return dist[t];
}
int main(){
    
    int n, m; cin>>n>>m;
    while(m--){
        int a,b,c; cin>>a>>b>>c;
        vec[a].push_back({b, c});
        vec[b].push_back({a, c});
    }
    
    int s, t; cin>>s>>t;
    
    cout<<dijkstra(s, t);

    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐