[다익스트라] BOJ 1753 최단경로 (C++)

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

 

 

문제 해결 알고리즘

 

다익스트라를 써주는 문제.

 

하지만 노드의 수 제한이 20000까지이므로 그냥 선형탐색으로 풀면 무조건 시간초과가 날 수밖에 없다.

그렇기 때문에 우선순위 큐를 이용해 정답을 구하자.

 

아래의 링크에 다익스트라 알고리즘이 설명되어있다.

https://kimmessi.tistory.com/185?category=871925 

[알고리즘] 다익스트라 - 선형 탐색, 우선순위 큐

 

소스 코드

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

vector<pair<int, int>> graph[20001];
int V, E;

int d[20001];

void dijkstra(int start_node){
    
    priority_queue<pair<int ,int>> pq;

    pq.push({0, start_node});
    d[start_node] = 0;
    while(!pq.empty()){

        int dist = -pq.top().first;
        int now = pq.top().second;

        pq.pop();

        if(d[now] < dist) continue;

        for(int i=0;i<graph[now].size();i++){
            int cost = dist + graph[now][i].second;

            if(cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push({-cost, graph[now][i].first});
            }
        }

    }
}

int main(){

    int start_node;

    cin >> V >> E >> start_node;
    
    for(int i=0;i<E;i++){
        int a, b, c; 
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
    }

    fill(d, d+20001, INF);

    dijkstra(start_node);

    for(int i=1;i<=V;i++){
        if(d[i] == INF) cout << "INF\n";
        else cout << d[i] << '\n';
    }
}