최단경로 - 다익스트라 - 우선순위큐 사용

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int n, m, start;
vector<pair<int, int>> graph[100001];
bool visited[100001];
int d[100001];

int getSmallestNode(){
    int min_value = INF;
    int index = 0;
    for(int i=1; i<=n; i++){
        if(d[i] < min_value && !visited[i]){
            min_value = d[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(int start){
    priority_queue<pair<int, int> > pq;
    pq.push({0,start});
    d[start] = 0;

    if(d[now] < dist) continue;
    while(!pq.empty()){
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();

        for(int j=0; j<graph[now].size(); j++){
            int cost_via_now = d[now] + graph[now][j].second;
            if(cost_via_now < d[graph[now][j].first]){
                d[graph[now][j].first] = cost_via_now;
                pq.push(make_pair(-cost_via_now, graph[now][j].first));
            }
        }
    }

}


int main()
{

    cin >> n >> m >> start;

    for(int i=0; i<m; i++){
        int a, b, c;
        cin >> a >> b >>c;
        graph[a].push_back({b,c});
    }

    fill_n(d, 100001, INF);

    dijkstra(start);

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

    }
    return 0;
}


/*
입력 예시
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
*/