[c++] 백준 1753번: 최단경로

problem

문제 링크 : https://www.acmicpc.net/problem/1753

입력 : 정점의 개수, 간선의 개수, 단방향 그래프

출력 : i 번째 줄에 i번 정점으로 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF 를 출력한다.

solution

다익스트라 알고리즘을 통해 각 정점까지의 거리를 구하고 출력한다.

code

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

using namespace std;
vector<vector<pair<int, int>>> node;
vector<int>d;

void dijkstra(int start) {
    d[start] = 0;
    priority_queue<pair<int, int>> q;
    q.push(make_pair(0, start));
    while (!q.empty()) {
        int now = q.top().second;
        //음수로 넣었던 값을 다시 양수로 바꾼다
        int dis = -q.top().first;
        q.pop();
        if(d[now] < dis)continue;

        for(int i = 0; i < node[now].size(); i++){
            int next = node[now][i].second;
            int nd = dis + node[now][i].first;
            if(nd < d[next]){
                d[next] = nd;
                //우선순위 큐에서 작은 값을 먼저 선택할 수 있도록 음수거리를 넣는다
                q.push(make_pair(-nd, next));
            }
        }
    }

}

int main()
{
    //입출력 가속기
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int v, e, k;
    cin >> v >> e >> k;
    d.resize(v, INF);
    node.resize(v);
    for(int i = 0; i < e; i++){
        int n1, n2, l;
        cin >> n1 >> n2 >>l;
        n1--;
        n2--;
        node[n1].push_back(make_pair(l,n2));
    }
    dijkstra(k-1);
    for(int i : d){
        if(i == INF){ cout << "INF" << ' '; continue;}
        cout << i << ' ';
    }
}