[백준 5972] 택배 배송 (C++)

문제 링크: https://www.acmicpc.net/problem/5972

5972번: 택배 배송

1. 주의할 점

- 다익스트라 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- 1번 Node부터 각 Node까지의 거리를 MAX로 초기화한다

- 간선에 대한 정보를 V[] 벡터에 담는다

- 우선순위큐를 사용하여 다익스트라 알고리즘을 구현한다

#define MAX 987654321
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct info{
    int idx,val;
};
struct cmp{
    bool operator()(info &a, info &b){
        return a.val > b.val;
    }
};
vector<info> v[50001];
int node, edge,a,b,val,result;
int dist[50001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>node>>edge;
    //초기화
    for(int i=1;i<=node;i++)
        dist[i]=MAX;
    
    for(int i=0;i<edge;i++){
        cin>>a>>b>>val;
        v[a].push_back({b,val});
        v[b].push_back({a,val});
    }
    priority_queue<info,vector<info>,cmp> pq;
    dist[1]=0;
    pq.push({1,0});
    while(!pq.empty()){
        int cidx = pq.top().idx;
        int cv = pq.top().val;
        pq.pop();
        if(cidx==node){
            result=cv;
            break;
        }
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i].idx;
            int nv = v[cidx][i].val;
            if(dist[next]>cv+nv){
                dist[next]=cv+nv;
                pq.push({next,cv+nv});
            }
        }
    }
    cout<<result;
    return 0;
}