백준 1753 <최단경로> C++

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

1753번: 최단경로

---

다익스트라 알고리즘을 사용해 풀 수 있습니다.

---

#include <iostream>

#include <array>

#include <vector>

#include <deque>

#include <algorithm>

using namespace std;

/*

다익스트라 함수를 사용

*/

array<int, 20001> dijkstra(array<vector<array<int, 2>>, 20001> tree, int K, int V)

{

    // 시스템상 최대 수 한계

    const int max_num = 3000001;

    // K 부터 특정 노드까지의 거리 어레이

    array<int, 20001> dist_arr;

    // 최대 수로 채우기

    dist_arr.fill(max_num);

    // 시작 노드까지 거리는 0

    dist_arr[K] = 0;

   

    // 힙에 넣기

    deque<array<int, 2>> dq{ {0, K} };

    make_heap(dq.begin(), dq.end());

    // 힙이 빌때까지 순회

    while (!dq.empty())

    {

        // 팝

        int now_dist = -dq.front()[0];

        int now_node = dq.front()[1];

        dq.pop_front();

        // 현재 거리와 기록된 거리 비교

        if (now_dist > dist_arr[now_node]) continue;

        // 자식 노드 순회하며 비교

        for (auto data : tree[now_node])

        {

            int next_node = data[0];

            int next_dist = data[1];

           

            // 다음 노드까지의 거리가 기록된 거리보다 크면 스킵

            if (now_dist + next_dist < dist_arr[next_node])

            {

                dq.push_back({ -(now_dist + next_dist), next_node });

                push_heap(dq.begin(), dq.end());

                dist_arr[next_node] = now_dist + next_dist;

            }

        }

    }

    return dist_arr;

}

int main(void)

{

    int V, E, K;

    cin >> V >> E >> K;

    // 트리 / tree[i] = { {자식 노드, 자식 노드까지의 거리} ... }

    array<vector<array<int, 2>>, 20001> tree;

    for (int i = 0; i < E; i++)

    {

        int u, v, w;

        cin >> u >> v >> w;

        tree[u].push_back({ v, w });

    }

    array<int, 20001> dist_arr = dijkstra(tree, K, V);

    for (int i = 0; i < V; i++)

    {

        if (dist_arr[i + 1] == 3000001) cout << "INF" << "\n";

        else cout << dist_arr[i + 1] << "\n";

    }

}