최단 경로

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
 
using namespace std;
class PAIR {
public:
    int x, y;
    PAIR(int x, int y) {
        this->x = x;
        this->y = y;
 
    }
};
int tc,n, d, c;
vector<PAIR> map[20000];
int visit[20000];
//bool dist[20000];
int node, edge;
int INF = 987654321;
int dist[20000];
 
 
void dijkstra(int start) {
    visit[start] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push(make_pair(0,start));
    while (!pq.empty()) {
        int current = pq.top().second;
        int distance = -pq.top().first;
        pq.pop();
        //if (visit[current] < distance) continue;
        for(int i = 0; i< map[current].size(); i++){
            int next = visit[current] + map[current][i].y;
            int before = visit[map[current][i].x];
            if (next < before) {
                visit[map[current][i].x] = next;
                pq.push(make_pair( -next,map[current][i].x));
            }
        }
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> node >> edge;
    int start;
    cin >> start;
    for (int i = 0; i < node; i++) {
        visit[i] = INF;
    }
    for (int i = 0; i < edge; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        map[a - 1].push_back(PAIR(b-1,c));
        //map[b - 1].push_back({ a - 1,c });
 
    }
    
    dijkstra(start-1);
    for (int i = 0; i < node; i++) {
        if (visit[i] != INF)
            cout << visit[i] << '\n';
        else
            cout << "INF" << '\n';
    }
    return 0;
}

마찬가지로 다익스트라 알고리즘이다.

주의해야할게, 경로의 가치의 크기에 따른 우선순위 큐이기때문에, first와 second의 위치가 바뀌어야한다