BOJ 1753 - 최단경로

문제 태그 : https://www.acmicpc.net/problem/1753

문제 설명

 이 문제에서 요구하는 것은 방향그래프에서 특정 정점이 주어졌을 때 그 점으로부터 모든 점까지의 거리를 각각 구하는 것이다. 이는 다익스트라 알고리즘이 하는 일과 정확히 일치한다. 맞다. 다익스트라를 한번 연습해보라는 뜻이다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
 
vector<pii> edg[20202];
ll dis[303030];
ll inf=1e18;
 
void dijk(ll st){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,st});
    while(!pq.empty()){
        auto x = pq.top(); pq.pop();
        if(dis[x.ss]<x.ff) continue;
        for(auto n : edg[x.ss]){
            if(dis[x.ss]+n.ff<dis[n.ss]){
                dis[n.ss]=dis[x.ss]+n.ff;
                pq.push({dis[n.ss],n.ss});
            }
        }
    }
}
 
int main(){
    ll i,j,k,l,m,n,u,v,c;
    scanf("%lld %lld %lld",&n,&m,&k);
    for(i=1;i<=n;i++)
        if(i!=k)
            dis[i]=inf;
    for(i=1;i<=m;i++){
        scanf("%lld %lld %lld",&u,&v,&c);
        edg[u].emplace_back(c,v);
    }
    dijk(k);
    for(i=1;i<=n;i++){
        if(dis[i]==inf) printf("INF\n");
        else printf("%lld\n",dis[i]);
    }
}