[백준] 1753번: 최단 경로 / C++

✏️ 문제 링크

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

1753번: 최단경로

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

 

 

 

✏️ 문제 풀이

이전 게시글 참고! 🦄

2021.09.15 - [Algorithm 🧠/알고리듬(thm) 공부 🌱] - [백준] 1916: 최소비용 구하기/ 다익스트라 / C++ ⭐

[백준] 1916: 최소비용 구하기/ 다익스트라 / C++ ⭐

 

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
using pii=pair<int, int>;

#define MAX 20001
#define INF 987654321


vector<pii> vec[MAX];
vector<int> dist(MAX, INF);

void dijkstra(int start){
    dist[start]=0;
    priority_queue<pii> pq; pq.push({0, start});
    
    while(!pq.empty()){
        pii t=pq.top(); pq.pop();
        int v=t.second; int w=t.first * -1;
        
        if(dist[v]<w) continue;
        
        for(int i=0; i<vec[v].size(); i++){
            int nxt=vec[v][i].first;
            int nxt_dist=vec[v][i].second + w;
            
            if(nxt_dist<dist[nxt]){
                dist[nxt]=nxt_dist;
                pq.push({nxt_dist*-1, nxt});
            }
        }
    }

}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int V, E; cin>>V>>E;
    int start; cin>>start;
    
    
    while(E--){
        int u,v,w; cin>>u>>v>>w;
        vec[u].push_back({v, w});
    }
    
    
    dijkstra(start);
    
    for(int i=1; i<=V;i++){
        if(dist[i]!=INF) cout<<dist[i];
        else cout<<"INF";
        cout<<"\n";
    }
    
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐