백준 26125번: 두 도로 (C++)

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

26125번: 두 도로

---

Level: Gold III
Solved By: Floyd Warshall

각 쿼리마다 다익스트라를 쓰기에는 총 시간 복잡도는 O(Q * ElogV)로 시간 초과를 받게 됩니다. 그래서 오프라인 쿼리 같은 방법이 있을까 했지만, 떠오르지 않았습니다. 여기서 문제점은 '최단 경로들을 가지고 있는 배열이나 자료구조에서 쿼리가 주어질 때마다 어떻게 변형을 시킬까?'가 발목을 붙잡는 것이었습니다. 왜냐하면, 변형을 시킨 뒤 다시 새로운 쿼리를 처리할 땐 예전 최단 경로 배열이나 자료구조의 값들을 가지고 있어야 했기 때문입니다.

결론지어 말하면 굳이 변형(업데이트)을 시킬 필요가 없다는 생각을 갇는 게 중요했습니다. 그래서 플로이드 와샬을 떠올렸습니다. 방법은 예를 들어 설명할 수 있습니다.

graph라는 플로이드 와샬을 돌린 2차원 배열이 있다고 합시다. 그때, S와 T의 최단 경로는 graph[S][T]가 될 것입니다. 이때 a와 b사이의 경로 값이 c라고 주어지고, a와 b 경로를 사용한 S와 T사이의 최단 경로 값을 알고 싶다면, graph[S][a] + c + graph[b][T]라고 표현하면 됩니다. 이게 이번 문제의 핵심입니다.

이제 각 쿼리가 주어졌을 때, 다음 경우들을 따지면 됩니다.
1) Edge를 하나만 사용할 때
2) Edge를 둘 다 사용할 때

1번은 쉽게 처리하지만, 저는 2번에서 따져야 할 경우를 하나 놓쳐서 여러 번 틀렸습니다.
a1, b1, c1, a2, b2, c2가 주어지면, graph[S][a1] + c1 + graph[b1][a2] + c2 + graph[b2][T] 여기까지는 생각했지만, 하나의 방법이 더 있다는 걸 알지 못 했습니다. 즉, 2번째 Edge를 먼저 지나가며 1번째 Edge까지 지나가는 방법은 놓쳤던 겁니다.

그러면 graph[S][a2] + c2 + graph[b2][a1] + c1 + graph[b1][T]까지 고려해주면 정답이 됩니다.

(+어젯밤 행군 도중 풀이가 생각나서 마치고 난 후, 자고 일어나서 바로 사지방으로 달렸습니다😆)

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <complex>
#include <string>
#include <climits>
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define INF 3e9
#define MAX 301
using namespace std;
typedef complex<double> cpx;
typedef pair<int, int> pii;

int N, M, S, T;
ll graph[MAX][MAX];

void floydWarshall(){
    for(int k = 1; k <= N; k++){
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                if(i == k || k == j) continue;
                if(graph[i][k] + graph[k][j] < graph[i][j]){
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

ll min_(ll a, ll b){
    if(a < b) return a;
    else return b;
}

int main(){
    FASTIO
    cin >> N >> M >> S >> T;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if(i == j) continue;
            graph[i][j] = INF;
        }
    }
    
    for(int i = 0; i < M; i++){
        int a, b; ll c; cin >> a >> b >> c;
        graph[a][b] = min_(graph[a][b], c);
    }
    
    floydWarshall();
    
    int Q; cin >> Q;
    
    while(Q--){
        int a, b, d, e;
        ll c, f;
        cin >> a >> b >> c >> d >> e >> f;
        
        ll res = INF;
        res = min_(res, graph[S][T]);
        res = min_(res, graph[S][a] + c + graph[b][T]); // use 1 edge
        res = min_(res, graph[S][d] + f + graph[e][T]); // use 1 edge
        res = min_(res, graph[S][a] + c + graph[b][d] + f + graph[e][T]); // use 2 edges
        res = min_(res, graph[S][d] + f + graph[e][a] + c + graph[b][T]); // use 2 edges
        
        if(res == INF) cout << -1;
        else cout << res;
        cout << '\n';
    }
    return 0;
}