(라이님 블로그 대회 알고리즘 따라잡기 16) 다익스트(Dijkstra's Algorithm)

D 아이 제이 케이 스트라 알고리즘을 공부해보았다! 이것도 매우 유명한 알고리즘 중 하나!

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220796029558&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

다익스트라 알고리즘(Dijkstra's Algorithm) (수정: 2019-08-16)

 

라이님 알고리즘을 보다가 gpt가 조금 고쳐준 버전으로 문제를 풀어볼까 한다!

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <climits>
using namespace std;

typedef pair<int, int> P; // first: 최단 거리, second: 노드 인덱스

void dijkstra(int V, int start, const vector<vector<P>>& adj) {
    vector<int> dist(V, INT_MAX);
    priority_queue<P, vector<P>, greater<P>> pq;

    dist[start] = 0;
    pq.emplace(0, start);

    while (!pq.empty()) {
        int curr_dist = pq.top().first;
        int curr = pq.top().second;
        pq.pop();

        if (dist[curr] < curr_dist) continue;

        for (const auto& edge : adj[curr]) {
            int next = edge.first, weight = edge.second;
            if (dist[next] > dist[curr] + weight) {
                dist[next] = dist[curr] + weight;
                pq.emplace(dist[next], next);
            }
        }
    }

    for (int i = 0; i < V; ++i) {
        if (dist[i] == INT_MAX)
            cout << "INF\n";
        else
            cout << dist[i] << "\n";
    }
}

int main() {
    int V, E, K;
    cin >> V >> E >> K;
    vector<vector<P>> adj(V);

    for (int i = 0; i < E; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u - 1].emplace_back(v - 1, w);
    }

    dijkstra(V, K - 1, adj); // K-1 to convert to 0-indexed
    return 0;
}

 

gpt... 진짜 잘한다...

ㅋㅋㅋㅋㅋㅋㅋ

 

알려준 템플릿으로 오늘 다익스트라 알고리즘 시작!