[백준 1753] 최단경로

🔗 알고리즘 문제

다익스트라를 공부한 후 확인 차 풀어본 문제. 다익스트라의 기본 개념 문제라고 볼 수 있기에 쉽게 해결할 수 있었다.

문제 분석

이 문제는 그래프의 정보와 시작 정점이 주어질 때 시작 정점에서 각 정점까지의 최단 경로를 출력하는 문제이다.

발상 & 알고리즘 설계

최단 경로를 구하는 다익스트라 알고리즘을 구현하는 문제라고 봐도 무방하기에 단순 다익스트라를 구현하여 해결하면 된다.

다익스트라에 관한 내용은 해당글을 참고하기
https://velog.io/@ehdbs28/다익스트라Dijkstra-알고리즘

코드

#include<iostream>
#include<queue>
#include<vector>
#include<climits>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);

    vector<pair<int, int>> graph[20001] = {};
    vector<int> check;

    int v;
    int e;
    int s;

    cin >> v >> e >> s;

    check = vector<int>(v, INT_MAX);

    for(int i = 0; i < e; i++){
        int v1, v2, dis;
        cin >> v1 >> v2 >> dis;
        graph[v1].emplace_back(v2, dis);
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.emplace(0, s);
    check[s - 1] = 0;

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

        for(int i = 0; i < graph[node.second].size(); i++){
            pair<int, int> next = graph[node.second][i];

            if(node.first + next.second < check[next.first - 1]){
                check[next.first - 1] = node.first + next.second;
                pq.emplace(node.first + next.second, next.first);
            }
        }
    }

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