[백준] 5972번: 택배 배송 / C++

✏️ 문제 링크

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

5972번: 택배 배송

 

 

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

 

✏️ 문제 풀이

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

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

 

👆🏻 위의 링크 먼저 이해 후 풀면 쉽게 풀린다 :)

 

✏️ 문제 코드

#include <bits/stdc++.h>

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

#define MAX 50001
#define INF 987654321

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


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

 

 

 

 ⭐ if feedback and question : comment please⭐