Baekjoon 1753 (최단 경로)

Baekjoon 1753, 백준 1753 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
#define INF 999999999

int V, E, K;
int dist[20002];     // dist[i] : minimum distance going to node i, gets updated
vector< pair<int,int> > map[20002];     // connected node information : {to,value}

void Dijkstra() {
    // Dijkstra Algorithm using priority_queue
    priority_queue< pair<int,int> > pq;
    pq.push( make_pair(0,K) );
    dist[K] = 0;

    while(!pq.empty()) {
        int current_node = pq.top().second;
        int cost = (-1) * pq.top().first;   // to use priority_queue as minimum heap
        pq.pop();

        // update values of dist
        for(int i = 0; i < map[current_node].size(); i++){
            int test_node = map[current_node][i].first;
            int new_cost = cost + map[current_node][i].second;
            int before_cost = dist[test_node];

            // if new_cost < before_cost, update
            if(new_cost < before_cost) {
                dist[test_node] = new_cost;
                pq.push( make_pair(-1 * new_cost,test_node) );
            }
        }
    }
}

int main() {

    // put inputs & initialization
    scanf("%d %d", &V, &E);
    scanf("%d", &K);

    while(E--){
        int from, to, value ;
        scanf("%d %d %d", &from, &to, &value);
        map[from].push_back(make_pair(to,value));
    }

    for(int i = 1; i <= V; i++)
        dist[i] = INF;

    // solution by Dijkstra Algorithm
    Dijkstra();

    // print
    for(int i = 1; i <= V; i++){
        if(dist[i] != INF) printf("%d\n", dist[i]);
        else printf("INF\n");
    }
}

기본적인 다익스트라 알고리즘 (Dijkstra Algorithm) 의 구현이다.
시간복잡도를 줄이기 위해 우선순위큐(priority queue)를 사용하였으며, 우선순위큐를 최소 힙으로 사용하기 위해 첫 번째에 -1을 곱해 주었다.

다익스트라 알고리즘에 대한 이론은 여기에서 확인할 수 있다.