Programming/BOJ

[백준/BOJ] 1753 최단경로

he1fire 2020. 9. 26. 01:15
728x90

문제 : 1753 최단경로

 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.

www.acmicpc.net

방향 그래프가 주어졌을 때, 시작점에서 다른 모든 점까지의

최단경로를 구해 출력하는 문제이다.

Dijkstra 알고리즘을 사용해 순회한 후 경로가 존재하는지

체크해 배열의 값을 출력하면 된다.

 


Code

#include <bits/stdc++.h>
#define ll long long
#define INF 987654321
using namespace std;
typedef pair<ll,ll> pll;
struct ABC
{
    ll idx, dst;
    ABC(){}
    ABC(ll idx, ll dst): idx(idx), dst(dst) {}
};
bool operator<(ABC a, ABC b){
    return a.dst>b.dst;
}
ll V, E, K, visit[20005];
vector<ABC> arr[20005];
priority_queue<ABC> pq;
void Dijkstra(){
    fill(&visit[0], &visit[20004], INF);
    pq.push(ABC(K,0));
    visit[K]=0;
    while (!pq.empty()){
        ll curr=pq.top().dst, x=pq.top().idx; 
        pq.pop();
        if (visit[x]<curr)
            continue;
        for (int i=0;i<arr[x].size();i++){
            ll next=arr[x][i].dst, dx=arr[x][i].idx;
            if (visit[dx]>curr+next){
                visit[dx]=curr+next;
                pq.push(ABC(dx,curr+next));
            }  
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> V >> E >> K;
    for (int i=0;i<E;i++){
        ll a, b, c;
        cin >> a >> b >> c;
        arr[a].push_back(ABC(b,c));
    }
    Dijkstra();
    for (int i=1;i<=V;i++){
        visit[i]==INF ? cout << "INF\n" : cout << visit[i] << "\n";
    }
    return 0;
}
728x90