[백준 5972번] 택배 배송

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

5972번: 택배 배송

<문제 풀이> 다익스트라 알고리즘

 

다익스트라 알고리즘을 사용해서 출발지부터 도착지까지의 최단거리를 구하면 됩니다.

 

 

<C++소스코드>

 

#include<iostream>
#include<vector>
#include<utility>
#include<cstring>
#include<queue>
#include<functional>
using namespace std;

const int MAX_N = 50000;

int N, M;
vector<pair<int, int> > adj[MAX_N + 1];
int d[MAX_N + 1];
int dijkstra(int start, int end) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    memset(d, 0x3f, sizeof(d));

    d[start] = 0;
    pq.push({ d[start], start });
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        int dist = cur.first;
        int curIdx = cur.second;
        if (d[curIdx] != dist) continue;
        for (auto& nxt : adj[curIdx]) {
            int cost = nxt.first;
            int nIdx = nxt.second;
            if (d[curIdx] + cost < d[nIdx]) {
                d[nIdx] = d[curIdx] + cost;
                pq.push({ d[nIdx], nIdx });
            }
        }
    }
    return d[end];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({ w, v });
        adj[v].push_back({ w, u });
    }

    cout << dijkstra(1, N);


    return 0;
}