[BOJ/Gold 4] 백준 1504 특정한 최단 경로(C++)

문제 링크

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

1504번: 특정한 최단 경로

 

 

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1

7

알고리즘 분류

• 최단 거리 알고리즘

풀이

1번 정점에서 시작해서 N번 정점까지 이동해야 한다. 그런데 A와 B번 정점을 거쳐야 한다.

그렇게 이동할 수 있는 경우의 수는 다음과 같다.

1 → A → B → N

1 → B → A → N

이 2가지 경우에서 가능한 최단 경로를 구하고, 2가지를 비교하여 비용이 더 낮은 값을 출력한다.

그러기 위해서는 다익스트라를 총 3번 수행해야 한다. 우선순위 큐를 사용한 다익스트라의 시간 복잡도는 O(ElogV)이고, 최악의 경우에도 연산이 1초를 넘지 않는다.

첫 다익스트라는 1번 정점에서 시작하여 ① 1 → A일 때의 최단 거리와, ② 1 → B일 때의 최단 거리를 구한다.

그 다음 다익스트라는 A번 정점에서 시작하여 ③ A → B일 때의 최단 거리와, ④ A → N일 때의 최단 거리를 구한다.

마지막 다익스트라는 B번 정점에서 시작하여 ⑤ B → N일 때의 최단 거리를 구한다.

1 → A → B → N일 때는 ① + ③ + ⑤를, 1 → B → A → N일 때는 ② + ③ + ④를 구하고 둘의 값을 비교해 최솟값을 출력한다.

혹시 둘 중에 하나라도 값이 정해지지 않는다면 값이 정해진 다른 최단 거리를 출력하면 되고, 둘 다 값이 정해지지 않는다면 -1을 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 801
#define INF 2e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0);

using namespace std;
int N, E, V1, V2;
vector<pair<LL, int> > Edge[MAX];
LL Dist[MAX];
LL one2A, one2B, a2B, a2N, b2N, Answer1, Answer2;

void input() {
    cin >> N >> E;
    for (int i = 0; i < E; i++) {
        int A, B;
        LL C;
        cin >> A >> B >> C;
        Edge[A].push_back(make_pair(B, C));
        Edge[B].push_back(make_pair(A, C));
    }
    cin >> V1 >> V2;
}

void init() {
    for (int i = 0; i <= N; i++) {
        Dist[i] = INF;
    }
}

void dijkstra(int A) {
    priority_queue<pair<LL, int> > PQ;
    Dist[A] = 0;
    PQ.push(make_pair(0, A));

    while (!PQ.empty()) {
        LL CurD = -PQ.top().first;
        int CurX = PQ.top().second;
        PQ.pop();

        if (Dist[CurX] < CurD) {
            continue;
        }

        for (int i = 0; i < Edge[CurX].size(); i++) {
            LL NextD = Edge[CurX][i].second;
            int NextX = Edge[CurX][i].first;
            if (Dist[NextX] > CurD + NextD) {
                Dist[NextX] = CurD + NextD;
                PQ.push(make_pair(-Dist[NextX], NextX));
            }
        }
    };
}

void settings() {
    init();
    dijkstra(1);
    one2A = Dist[V1]; // 1
    one2B = Dist[V2]; // 2
    init();
    dijkstra(V1);
    a2B = Dist[V2]; // 3
    a2N = Dist[N]; // 4
    init();
    dijkstra(V2);
    b2N = Dist[N]; // 5
    // 1 + 3 + 5와 2 + 3 + 4를 비교해서 최솟값을 구한다. 둘 다 INF이면 -1을 출력.
    Answer1 = one2A + a2B + b2N;
    if ((one2A == INF) || (a2B == INF) || (b2N == INF)) {
        Answer1 = -1;
    }
    Answer2 = one2B + a2B + a2N;
    if ((one2B == INF) || (a2B == INF) || (a2N == INF)) {
        Answer2 = -1;
    }
}

void find_Answer() {
    if ((Answer1 == -1) && (Answer2 != -1)) {
        cout << Answer2 << "\n";
    }
    else if ((Answer1 != -1) && (Answer2 == -1)) {
        cout << Answer1 << "\n";
    }
    else if ((Answer1 != -1) && (Answer2 != -1)) {
        cout << min(Answer1, Answer2) << "\n";
    }
    else {
        cout << "-1\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}