[백준] 5972번: 택배 배송

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

5972번: 택배 배송

전형적인 최소 거리 찾는 알고리즘이고, 플로이드 와샬과 다익스트라 알고리즘 중 다익스트라 알고리즘을 선택하면 된다.

왜냐하면 출발점과 도착점이 각각 하나씩 정해져있기 때문이다.

 

그런데 구현 과정에서 자꾸 반복적으로 Queue의 내부 자료구조에 임의의 점과 해당 점까지의 출발점으로부터의 거리를 pair를 써서 같이 넣으려고 하는데, 그럴 필요가 없다!!!!

왜냐하면 dist라는 배열에 가장 최신의 거리를 기록해두기 때문이다.

따라서 Queue 설정하느라 시간 뺏지 않아도 된다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> q;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> cows(n + 1);
    vector<int> dist(n + 1,50000 * 1000);
    for(int i = 0;i < m;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        cows[a].push_back({b, c});
        cows[b].push_back({a, c});
    }
    
    q.push(1);
    dist[1] = 0;
    while(!q.empty()) {
        int cur_pos = q.top();
        q.pop();
        
        for(int i = 0;i < cows[cur_pos].size();i++) {
            int next_pos = cows[cur_pos][i].first;
            int next_dist_part = cows[cur_pos][i].second;
            if(dist[next_pos] > dist[cur_pos] + next_dist_part) {
                dist[next_pos] = dist[cur_pos] + next_dist_part;
                q.push(next_pos);
            }
        }
    
    }
    
    cout << dist[n] << '\n';
}