[그래프(다익스트라)] 백준 1753 최단경로 C++

 

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

시작 정점 하나로부터 최단 경로 찾음

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 20001
#define INF 1e18
using namespace std;

bool p;
long long a, b, c, cnt, v, e, k;
long long dist[MAX];
vector<pair<long long, long long>> vec[MAX];
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<>> pq;

int main(void) {
    scanf("%d %d", &v, &e);
    scanf("%d", &k);

    for (int i = 0; i < e; i++) {
        scanf("%d %d %d", &a, &b, &c);
        vec[a].push_back({ b,c });
    }

    fill(dist, dist + v + 1, INF);
    pq.push({ 0,k });
    while (pq.size()) {
        auto now = pq.top();
        pq.pop();
        if (dist[now.second] < now.first) continue;
        for (auto i : vec[now.second])
        {
            if (dist[i.first] <= now.first + i.second) continue;
            dist[i.first] = now.first + i.second;
            pq.push({ dist[i.first], i.first });
        }
    }

    for (int i = 1; i <= v; i++) {
        if (i == k) printf("0\n");
        else if (dist[i] == INF) printf("INF\n");
        else printf("%d\n", dist[i]);
    }
}