[BOJ/Gold 3] 백준 26125 두 도로(C++)

문제 링크

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

 

 

문제

울산에는 1번부터 N번까지 번호가 붙은 N개의 교차로가 있고, 교차로와 교차로를 잇는 M개의 도로가 있다. 각 도로는 일방통행이며, 도로를 따라 이동하는 데 걸리는 시간이 정해져 있다.

윤이는 매일 현대모비스의 자율주행 시스템을 탑재한 차를 타고 집에서 회사로 출근한다. 윤이의 집은 S번 교차로에, 회사는 T번 교차로에 있다. 현대모비스의 자율주행 시스템은 항상 집에서 회사까지 최단 시간이 걸리는 주행 경로를 이용한다.

윤이는 얼마 전 울산에 새로운 도로 두 개가 건설될 것이라는 계획을 들었다. 윤이는 앞으로 회사에 더 빠르게 출근할 수 있을 거라는 기대감에 부풀어 있다. 하지만 윤이는 새 도로가 어떤 교차로를 잇는지와, 새 도로를 따라 이동하는 데 걸리는 시간이 얼마인지에 대한 내용을 듣지는 못했다. 따라서 윤이는 Q개의 도로 건설 시나리오를 가정하고, 각 상황에서 윤이의 자율주행차가 어떤 경로를 따라 주행할지 계산해 보기로 했다.

윤이가 가정한 Q개의 도로 건설 시나리오 각각에 대해, 윤이가 현대모비스 자율주행 시스템을 이용하여 집에서 회사로 출근하는 데 걸리는 시간을 구하시오.

입력

첫 번째 줄에 교차로의 수 N, 기존 도로의 수 M, 집의 교차로 번호 S, 회사의 교차로 번호 T가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300; 0 ≤ M ≤ 3,000; 1 ≤ S, T ≤ N; S ≠ T)

이후 M개의 줄에 기존 도로에 대한 정보를 나타내는 정수 u, v, w가 공백으로 구분되어 주어진다. 시작 교차로가 u번, 도착 교차로가 v번이고 이동하는 데 w의 시간이 걸리는 일방통행 도로를 나타낸다. (1 ≤ u, v ≤ N; 1 ≤ w ≤ 10^6)

그 다음 줄에 도로 건설 시나리오의 수 Q가 주어진다. (1 ≤ Q ≤ 100,000)

이후 Q개의 줄에 새로 건설될 두 개의 도로에 대한 정보를 나타내는 정수 a1, b1, c1, a2, b2, c2가 공백으로 구분되어 주어진다. 시작 교차로가 a1번, 도착 교차로가 b1번이고 이동하는 데 c1의 시간이 걸리는 일방통행 도로와, 시작 교차로가 a2번, 도착 교차로가 b2번이고 이동하는 데 c2의 시간이 걸리는 일방통행 도로를 새롭게 건설하는 시나리오를 나타낸다. (1 ≤ a1, b1, a2, b2 ≤ N; 1 ≤ c1, c2 ≤ 10^6)

같은 교차로 쌍을 잇는 도로가 여러 개 주어질 수 있으며, 시작 교차로와 도착 교차로가 동일한 도로가 주어질 수 있다.

출력

각 도로 건설 시나리오에 대해, 윤이가 집에서 회사로 출근하는 데 걸리는 시간을 Q개의 줄에 걸쳐 출력한다. 만약 어떤 시나리오에서 집에서 회사로 출근하는 것이 불가능하다면, 해당 줄에는 대신 −1을 출력한다.

예제 입력 1

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

예제 출력 1

5
7
6
7

알고리즘 분류

• 최단 거리 알고리즘

풀이

DP[S][T]를 S에서 T까지 가는 최단 거리라고 하였을 때, DP[S][T]의 최솟값을 갱신할 수 있는 경우의 수는 4가지이다.

1. S -> 도로 1 -> T

2. S -> 도로 2 -> T

3. S -> 도로 1 -> 도로 2 -> T

4. S -> 도로 2 -> 도로 1 -> T

갱신된 최솟값과 다음과 같이 4가지 경우에서 나올 수 있는 값을 비교하여 S에서 T까지 가는 최단 거리를 구한다.

최솟값을 갱신할 수 없어 무한대로 나온다면 -1을 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 301
#define INF 3e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, S, T, U, V, Q, A1, B1, A2, B2;
LL W, C1, C2;
LL DP[MAX][MAX];
LL Answer;

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (i == j) {
                continue;
            }
            DP[i][j] = INF;
        }
    }
}

void settings() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    continue;
                }
                if (DP[i][j] > DP[i][k] + DP[k][j]) {
                    DP[i][j] = DP[i][k] + DP[k][j];
                }
            }
        }
    }
}

void find_Answer() {
    Answer = DP[S][T];
    Answer = min(Answer, DP[S][A1] + min(C1, DP[A1][B1]) + DP[B1][T]);
    Answer = min(Answer, DP[S][A2] + min(C2, DP[A2][B2]) + DP[B2][T]);
    Answer = min(Answer, DP[S][A1] + min(C1, DP[A1][B1]) + DP[B1][A2] + min(C2, DP[A2][B2]) + DP[B2][T]);
    Answer = min(Answer, DP[S][A2] + min(C2, DP[A2][B2]) + DP[B2][A1] + min(C1, DP[A1][B1]) + DP[B1][T]);
    if (Answer == INF) {
        cout << "-1\n";
        return;
    }
    cout << Answer << "\n";
}

void input() {
    cin >> N >> M >> S >> T;
    while (M--) {
        cin >> U >> V >> W;
        DP[U][V] = min(DP[U][V], W);
    };
    settings();
    cin >> Q;
    while (Q--) {
        cin >> A1 >> B1 >> C1 >> A2 >> B2 >> C2;
        find_Answer();
    };
}

int main() {
    FASTIO
    init();
    input();

    return 0;
}