Dijkstra (다익스트라)

코드

문제 풀다가.. 생각나서 문서화 함

아래는 우선순위큐로 짠 코드

이 문서를 보는 신입이 고쳐줄거라 믿고있음 ㅇㅇ

#include <stdio.h>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>

using namespace std;

vector< pair<int, int> > g[801];

int dij(int s, int d) {
    priority_queue< pair<int, int> > q;
    int dist[801], i;

    memset(dist, 0x7F, sizeof(dist));
    dist[s] = 0;
    for ( i = 0; i < g[s].size(); i++ ) {
        q.push(make_pair(-g[s][i].second, g[s][i].first));
        dist[g[s][i].first] = g[s][i].second;
    }

    while( !q.empty() ) {
        pair<int, int> p = q.top();
        int w = -p.first;
        int v = p.second;
        q.pop();

        for ( i = 0; i < g[v].size(); i++ ) {
            pair<int, int> pu = g[v][i];
            int u = pu.first;
            int uw = dist[v] + pu.second;
            if ( dist[u] > uw ) {
                dist[u] = uw;
                q.push(make_pair(-uw, u));
            }
        }
    }

    return dist[d];
}

정리

• 우선순위큐로 시간복잡도를 줄임
  • 일반적인 구현 (인접리스트, 인접행렬) : O(E+V^2)
  • 우선순위큐 : O(E+VlogV)

참고 자료

• 종만북에 잘나옴
• 잉여로운 신입들이 적어줬으면 좋겠다

관련 문제

• 잉여로운 신입들이 적어줬으면 좋겠다