[ 백준 ] 1504 / 특정한 최단 경로

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
39/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 1504 / 특정한 최단 경로
 *
 * Kind :: Dijkstra
 *
 * Insight
 * - 경로 1: 1 -> v1 -> v2 -> N
 *   경로 2: 1 -> v2 -> v1 -> N
 *   이 두 경로중 무엇이 더 빠른가 하는 문제다
 *   + max(N)=800, max(E)=2*10^5 이니
 *     O(|E|log|E|) 시간복잡도의 다익스트라 알고리즘이라면
 *     6번 정도 돌려도 시간 제한내에 통과할 수 있을 것 같다
 *
 * Point
 * - 플로이드-워셜 알고리즘으로도 풀리긴 한다
 *
 * - 최단거리의 최대거리는 max(c)=1000 * max(N-1)=799 이므로
 *   799 * 1000 보다 큰 최단거리는 불가능하다
 *   + 그래서 INF 를 (800*1000+1) 로 설정했다
 *     # 경로 1에서 (1 -> v1) 은 10 인데 (v1 -> v2) 가 INF 가 나왔다면
 *       경로 1은 불가능한 경우이고, 거리는 INF 보다 커지게 된다
 *       -> 최악의 경우는 각 경로의 길이가 INF + INF + INF 가 되는 것인데
 *          Overflow 는 일어나지 않는다 (휴)
 *          => 즉, 각 경로가 불가능하다면 경로의 길이가 INF 이상이 된다
 *             이를 통해 가능여부를 판단해주자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N, E;
struct Node { int no, dist; };
struct State { int no, dist; };
vector<Node> A[800+1];
#define INF (800*1000+1)

// Set up : Functions Declaration
bool operator > (State &u, State &v);
int Dijkstra(int s, int e);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N >> E;
    for (int i=0; i<E; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        A[a].push_back({b, c});
        A[b].push_back({a, c});
    }
    int v1, v2;
    cin >> v1 >> v2;

    // Process
    int tmp1 = Dijkstra(1, v1) + Dijkstra(v1, v2) + Dijkstra(v2, N);
    int tmp2 = Dijkstra(1, v2) + Dijkstra(v2, v1) + Dijkstra(v1, N);
    int ans = min(tmp1, tmp2);

    // Control : Output
    cout << ((ans >= INF) ? -1 : ans) << endl;
}

// Helper Functions
bool operator > (State &u, State &v)
/* 구조체 State 비교를 위한 연산자 오버로딩 */
{
    return make_tuple(u.dist, u.no) > make_tuple(v.dist, v.no);
}

int Dijkstra(int s, int e)
/* 다익스트라 알고리즘을 활용하여
 * 정점 s 부터 정점 e 까지의 최단거리를 반환 */ 
{
    int dp[N+1];
    fill(&dp[1], &dp[N+1], INF);
    priority_queue<State,vector<State>,greater<>> pq;

    dp[s] = 0;
    pq.push({s, dp[s]});

    while (not(pq.empty())) {
        auto [c, cd] = pq.top();
        pq.pop();

        if (cd > dp[c]) continue;

        for (auto [n, d] : A[c]) {
            /* Relaxation */
            if (dp[n] > dp[c]+d) {
                dp[n] = dp[c]+d;
                pq.push({n, dp[n]});
            }
        }
    }

    return dp[e];
}
profile
이런 미친 게임을 봤나! - 옥냥이
post-custom-banner

0개의 댓글