BOJ 1753번 : 최단경로

다익스트라 알고리즘을 사용하는 문제이다.

이상하게도... 빠른 입출력을 사용하지 않으면 런타임 에러가 뜬다...ㅠ

다익스트라 알고리즘은 아래 글을 보면 된다.

https://00rigin.tistory.com/54

다익스트라(Dijkstra) 알고리즘

 

<소스코드>

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
 
using namespace std;
 
void dijkstra(vector<vector<pair<int,int>>> map, vector<int> d, int start ){
    
    d[start] = 0;
    priority_queue<pair<int,int>> pq; // 거리, 노드
    
    pq.push(make_pair(0, start));
    
    while(!pq.empty()){
        int cur = pq.top().second;
        int dist = pq.top().first * -1;
        pq.pop();
        
        if(d[cur] < dist) continue;
        
        for(int i = 0; i<map[cur].size(); i++){
            int next = map[cur][i].first;
            int next_dis = map[cur][i].second + dist;
            
            if(d[next] > next_dis){
                d[next] = next_dis;
                pq.push(make_pair(d[next]*-1, next));
            }
        }
    }
    
    for(int i = 1; i<d.size(); i++){
        if(d[i] == INT_MAX)
            cout<<"INF"<<endl;
        
        else
            cout<<d[i]<<endl;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    
    int n,e,start;
    
    cin>>n>>e; // 노드 간선
    cin>>start;
    
    vector<vector<pair<int,int>>> map(n+1);
    vector<int> d(n+1,INT_MAX);
    
    for(int i = 0; i<e; i++){
        int u,v,w;
        cin>>u>>v>>w;
        map[u].push_back(make_pair(v, w));
    }
    
    dijkstra(map, d, start);
    
}
 

<문제>

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

1753번: 최단경로