백준 5972번 택배 배송 C++

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

 

다익스트라

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;

struct VertexCost {
    int64 vertex;
    int64 cost;
    bool operator<(const VertexCost& other) const {
        return cost < other.cost;
    }
    bool operator>(const VertexCost& other) const {
        return cost > other.cost;
    }
};

vector<vector<pair<int64, int64>>> graph;

void Dijkstra(int64 start) {
    vector<int64> best(n + 1, INT_MAX);
    priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq;

    pq.push({ start,0 });
    best[start] = 0;

    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();

        if (curr.cost > best[curr.vertex]) continue;

        for (auto next : graph[curr.vertex]) {
            if (best[next.first] <= curr.cost + next.second) continue;

            best[next.first] = curr.cost + next.second;
            pq.push({ next.first,curr.cost + next.second });
        }
    }
    cout << best[n];
}

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

    cin >> n >> m;
    graph = vector<vector<pair<int64, int64>>>(n + 1, vector<pair<int64, int64>>());
    for (int i = 0; i < m; i++) {
        int64 start, end, cost;
        cin >> start >> end >> cost;
        graph[start].push_back({end,cost});
        graph[end].push_back({start,cost});
    }
    Dijkstra(1);
}