백준 1504 <특정한 최단 경로> C++

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

1504번: 특정한 최단 경로

---

다익스트라를 여러 번 사용해 풀 수 있습니다.

---

#include <iostream>

#include <array>

#include <vector>

#include <deque>

#include <algorithm>

using namespace std;

/*

다익스트라를 세번 사용

*/

// 다익스트라

int dijkstra(array<vector<array<int, 2>>, 801> tree, int N, int start, int end)

{

    // 시스템상 최대 거리

    int max_dist = 200000 * 1000 + 1;

   

    // 힙

    deque<array<int, 2>> hq{ {0, start} };

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

   

    // 개별 노드까지의 거리 최솟값

    array<int, 801> dist_arr;

    dist_arr.fill(max_dist);

    dist_arr[start] = 0;

    // 순회

    while (!hq.empty())

    {

        pop_heap(hq.begin(), hq.end());

        // 현재 노드, 거리

        int now_dist = -hq.back()[0];

        int now_node = hq.back()[1];

        hq.pop_back();

       

        // 현재 거리가 최소 길이보다 크면 패스

        if (now_dist > dist_arr[now_node]) continue;

        // 자식 순회

        for (auto node : tree[now_node])

        {

            int dist = node[1];

            int next_node = node[0];

            int next_dist = now_dist + dist;

            // 다음 거리가 다음 노드의 최소 길이보다 크면 패스

            if (next_dist < dist_arr[next_node])

            {

                hq.push_back({ -next_dist, next_node });

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

                dist_arr[next_node] = next_dist;

            }

        }

    }

    return dist_arr[end];

}

int main(void)

{

    int max_dist = 200000 * 1000 + 1;

    int N, E;

    cin >> N >> E;

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

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

    {

        int a, b, c;

        cin >> a >> b >> c;

        tree[a].push_back({ b, c });

        tree[b].push_back({ a, c });    

    }

    int V1, V2;

    cin >> V1 >> V2;

    // 두 경로를 비교하기 위해 둘 다 계산

    int dist_1 = dijkstra(tree, N, 1, V1) + dijkstra(tree, N, V1, V2) + dijkstra(tree, N, V2, N);

    int dist_2 = dijkstra(tree, N, 1, V2) + dijkstra(tree, N, V2, V1) + dijkstra(tree, N, V1, N);

    if (dist_1 >= max_dist and dist_2 >= max_dist) cout << -1;

    else if (dist_1 > dist_2) cout << dist_2;

    else cout << dist_1;

}