1753 ) 우선순위큐 이용한 다익스트라

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 210000000

using namespace std;
vector<pair<int, int> > adj[20001];
int dist[20001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i < 20001; i++)
        dist[i] = INF;

    int v, e, start;
    cin >> v >> e >> start;

    dist[start] = 0;
    for (int i = 0; i < e; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        adj[from].push_back(make_pair(cost, to));
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, start)); //시작하는 장소의 dist는 0

    while (!pq.empty()) {
        pair<int, int> cur = pq.top();
        pq.pop();

        //현재 갱신할 노드
        int curcost = cur.first;
        int curnode = cur.second;

        for (int i = 0; i < adj[curnode].size(); i++) {
            pair<int, int> now = adj[curnode][i];
            //갱신할 것의 인접한 노드들
            int newnode = now.second;
            int newcost = now.first;

            if (dist[newnode] > newcost + curcost) {
                dist[newnode] = newcost + curcost;
                pq.push(make_pair(newcost + curcost, newnode));
            }
        }
    }

    for (int i = 1; i <= v; i++) {
        if (dist[i] == INF)
            cout << "INF\n";
        else
            cout << dist[i] << "\n";
    }

    return 0;
}

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