[C/C++] 백준 #1753 최단경로(다익스트라)

이번 문제는 문제 자체가 다익스트라 알고리즘으로 푸는 문제입니다.

 

유향 그래프(directed graph)가 주어졌을 때, 시작점에서 출발해서, 다른 모든 노드들까지의 최단 경로를 찾는 것입니다.

정확하게 다익스트라 알고리즘입니다.

 

directed graph and adjacent list

 

저는 일단 해시맵(unordered map)을 이용해서 인접리스트를 구성했습니다.  그렇게 했던 가장 큰 이유는 두개의 정점사이에 두개 이상의 간선이 존재할 수 있다는 조건때문이었죠.  물론 벡터(vector)를 이용한다고 해서 문제가 되지는 않습니다.  최단거리이므로, 알아서 최소값을 찾아서 갈테니까요.  이것은 필수라기보다는 선택이라고 보입니다.

 

우선순위큐는 힙(heap) 자료구조를 이용해서 구현하였습니다.  우선순위큐를 바로 사용해도 괜찮은 선택입니다.  제 경우에는 힙을 직접 쓰는 것이 조금 더 편해서 힙을 사용한 것뿐입니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//---------------------------------------------
//    baekjoon #1753
//        - by Aubrey Choi
//        - created at 2019-09-12
//---------------------------------------------
#include <stdio.h>
#include <unordered_map>
#include <algorithm>
#define    INF    1000000

int node[20000];
int readint() {int s; scanf("%d",&s); return s; }
int MIN(int a, int b) { return a<b?a:b; }
bool cmp(long long a, long long b) { return a > b; }
int main()
{
    long long heap[300000]; int hp=0;
    static char v[20000];
    std::unordered_map<int,int> adj[20000];
    int n=readint(), m=readint(), s=readint()-1;
    for(int i=0;i<n;i++) node[i]=INF;
    while(m--)
    {
        int u=readint()-1, v=readint()-1, w=readint();
        adj[u][v]=(adj[u].find(v)!=adj[u].end())?MIN(adj[u][v],w):w;
    }
    heap[hp++]=s; node[s]=0;
    while(hp)
    {
        std::pop_heap(heap,heap+hp--,cmp);
        int s = heap[hp]&0xffff; if(v[s]) continue; v[s]=1;
        for(auto k : adj[s])
        {
            if(v[k.first]) continue;
            if(node[k.first] <= node[s]+k.second) continue;
            node[k.first]=node[s]+k.second;
            heap[hp++]=k.first|((long long)node[k.first]<<32);
            std::push_heap(heap, heap+hp, cmp);
        }
    }
    for(int i=0;i<n;i++) if(node[i]==INF) puts("INF"); else printf("%d\n", node[i]);
}