[백준 1602] 도망자 원숭이 C++

1602번: 도망자 원숭이

플로이드-와샬

---

 

쿼리(Q)가 최대 4만개 들어온다.

 

출발도시와 도착도시가 주어졌을 때 플로이드 최단경로를 구하고, 경로상의 정점 중 멍멍이가 괴롭힐 수 있는 최대 시간을 구한다면  O(40000 * N^3) 으로 시간초과가 발생한다.

 

플로이드의 특징을 잘 생각해보자

 

경유하는 점은 보통 1 ~ N 번까지의 점을 순서대로 경유하도록 한다.

이는 그냥 편의를 위해서 사용하는 순서이고 경유점의 순서가 바뀌더라도 결국 A->B로 가는 간선의 비용은 최솟값으로 맞춰지게된다.

 

그렇다면 경유하는 점의 순서를 원숭이가 방해받는 시간이 적은 순서부터 오름차순으로 정해야 한다.

방해 시간이 작은 정점부터 경유를 한다면 방해시간 + 이동시간을 최소로 하는 최단거리를 구할 수 있다.

 

경유 정점을 via 라고 하고 시작점과 도착점을 r, c라고 한다면 r, via, c의 방해 정보만 가지고 최단거리를 구할 수 있다.

방해 시간을 오름차순 정렬했기 때문에 r, via, c의 방해 정보만을 가지고 경로 시간을 계산해도 현재 경로상의 최대 방해 시간을 알 수 있다.

최단거리가 갱신이 된다면, 이는 지금까지 구한 경로중 r, via, c 중 최대 방해시간 + r -> via -> c 의 이동시간이 최소가 된다는 뜻이다.

 

예제 입력의 그래프

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M, Q;
pii Bulltime[501];
int dp[501][501];
int res[501][501];
pii Query[40001];
 
void input(){
    cin >> N >> M >> Q;
    for(int i = 1; i <= N; i++){
        cin >> Bulltime[i].first;
        Bulltime[i].second = i;
    }
    
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if(i == j){
                dp[i][j] = Bulltime[i].first;
                continue;
            }
            dp[i][j] = INF;
            res[i][j] = INF;
        }
    }
    
    int a, b, d;
    for(int i = 0; i < M; i++){
        cin >> a >> b >> d;
        dp[a][b] = d;
        dp[b][a] = d;
    }
    
    for(int i = 0; i < Q; i++){
        cin >> a >> b;
        Query[i] = {a, b};
    }
}
 
void solve(){
    for(int r = 1; r <= N; r++){
        for(int c = 1; c <= N; c++){
            // 자신이 도착점인 경우엔 자신의 방해시간이 걸리는 시간이 된다.
            if(r == c) res[r][c] = Bulltime[r].first;
            // r에서 c로가는 최소시간은 r에서 c로가는 거리의 최솟값 + r과 c중 더 오래걸리는 방해시간
            else res[r][c] = dp[r][c] + max(Bulltime[r].first, Bulltime[c].first);
        }
    }
    
    sort(Bulltime+1, Bulltime+N+1);
    
    // 정점 번호를 인덱스로 넣으면 해당 정점이
    // sort된 Bulltime의 몇 번 인덱스에 위치하는지 알 수 있다.
    int Bullidx[501];
    for(int i = 1; i <= N; i++){
        Bullidx[Bulltime[i].second] = i;
    }
    
    for(int i = 1; i <= N; i++){
        int via = Bulltime[i].second;
        for(int r = 1; r <= N; r++){             
            for(int c = 1; c <= N; c++){
                // via, r, c 정점 중 가장 긴 방해시간
                int delay = max(Bulltime[i].first, max(Bulltime[Bullidx[r]].first, Bulltime[Bullidx[c]].first));
                // 최단 거리 계산
                dp[r][c] = min(dp[r][c], dp[r][via] + dp[via][c]);
                // 최단 시간 계산
                res[r][c] = min(res[r][c], dp[r][via] + delay + dp[via][c]);
            }
        }
    }
    
    for(int i = 0; i < Q; i++){
        int ans = res[Query[i].first][Query[i].second];
        if(ans >= INF) cout << -1 <<"\n";
        else cout << ans << "\n";
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}