Algorithm in A..Z - Dijkstra

개념

최단거리를 구하는 알고리즘이다.

최단거리 + 최단거리 = 최단거리라는 그리디한 개념으로 최단거리를 찾는다.

=> 간선의 가중치가 음수인게 존재하면 다익스트라를 사용할 수 없다. (최단거리 + 최단거리 = 최단거리라는 보장이 깨지기 때문에)

---

작동원리

1. 시작 노드를 우선순위 큐에 넣는다.

2. 우선순위 큐에서 POP을한다.

3. POP한 노드가 최단거리이면 해당 노드에서 갈 수 있는 노드중 거리를 갱신하는 노드를 우선순위 큐에 PUSH한다.

4. 2 ~ 3을 우선순위 큐가 EMPTY가 될 때까지 한복한다.

---

시간복잡도

O(ElogV)

---

문제

11779 최소비용 구하기 2

www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

---

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int NONE = 0;

class Node {
public:
    int vertex, distance;

    Node(int vertex = 0, int distance = 0) : vertex(vertex), distance(distance) {

    }

    bool operator>(const Node &o) const {
        return distance > o.distance;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<Node>> map(n + 1);
    while (m--) {
        int source, destination, distance;
        cin >> source >> destination >> distance;

        map[source].emplace_back(destination, distance);
    }

    int source, destination;
    cin >> source >> destination;

    priority_queue<Node, vector<Node>, greater<>> que;
    vector<int> pre(n + 1, NONE);
    vector<long long> distance(n + 1, INT64_MAX);

    que.emplace(source, 0L);
    distance[source] = 0L;
    while (!que.empty()) {
        auto now = que.top(); que.pop();

        if (distance[now.vertex] == now.distance) {
            for (auto next : map[now.vertex]) {
                if (distance[next.vertex] > now.distance + next.distance) {
                    pre[next.vertex] = now.vertex;
                    distance[next.vertex] = now.distance + next.distance;
                    que.emplace(next.vertex, now.distance + next.distance);
                }
            }
        }
    }

    cout << distance[destination] << "\n";

    stack<int> st;
    while (destination != NONE) {
        st.emplace(destination);
        destination = pre[destination];
    }

    cout << st.size() << "\n";
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
}