음주 운전 단속 (DRUNKEN)

algospot.com :: DRUNKEN

플로이드-와샬

 

 

문제 설명

 

 

플로이드 알고리즘은 아무 정점도 경우하지 않는 최단 거리에서 시작해 경유할 수 있는 정점을 하나씩 추가해 가며 최단 거리를 갱신한다.

이 과정에서 경유하는 정점을 1번부터 순서대로 추가하지만, 이 순서가 뒤죽박죽이 되어도 알고리즘은 성립한다!

그리고 이 문제는 간선의 값만 비교해서 최단 경로를 구하더라도 단속 시간에 의해서 오히려 오래 걸릴 수 있기 때문에 어떤 점을 경유하는지가 더 중요하다.

 

a에서 b로가는 최소 예상 시간을 저장하는 2차원 배열을 하나 설정한다.

 

먼저 정점을 하나도 경유하지 않고 a에서 b로 다이렉트로 가는 최단 경로를 구한다.

시작점과 도착점에서 단속을 하지 않기 때문에 a와 b가 같은경우에는 0이 되고 a에서 b로가는길은 단순히 처음에 주어진 입력과 같게 된다.

 

그리고 각 정점별 단속시간을 오름차순으로 정렬해 준다.

단속에 시간이 적게 걸리는 정점부터 경유를 하면 항상 단속시간이 최소화된 값으로 플로이드 알고리즘을 수행하기 때문에 최단 경로를 올바르게 구할 수 있다.

 

본격적으로 a에서 b로가는 최단 경로를 구해보자

우선 3중 for문에서 일반적인 플로이드 최단거리를 구하듯이 a에서 b로가는 최단 거리를 갱신해 준다.

그리고 최소 예상 시간을 저장하는 배열에는

<기존에 구한 a에서 b로가는 최단 시간 vs a에서 b로가는데 현재 경유점의 단속시간을 더한 시간 값> 을 비교해서 더 작은 값으로 갱신해준다.

 

 

코드

#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 V, E, T;
pii crackdown[501];
int Graph[501][501];
int res[501][501];
pii output[1001];
 
void input(){
    int a, b, c;
    cin >> V >> E;
    for(int i = 1; i <= V; i++){
        cin >> a;
        crackdown[i] = {a, i};
    }
    
    for(int r = 1; r <= V; r++){
        for(int c = 1; c <= V; c++){
            Graph[r][c] = INF;
            res[r][c] = INF;
        }
    }
    for(int i = 0; i < E; i++){
        cin >> a >> b >> c;
        Graph[a][b] = c;
        Graph[b][a] = c;
    }
    
    cin >> T;
    for(int i = 0; i < T; i++){
        cin >> a >> b;
        output[i] = {a, b};
    }
}
 
void solve(){
    for(int i = 1; i <= V; i++){
        for(int j = 1; j <= V; j++){
            if(i == j) res[i][j] = 0;
            else res[i][j] = Graph[i][j];
        }
    }
    
    sort(crackdown+1, crackdown+V+1);
    
    for(int i = 1; i <= V; i++){
        int via = crackdown[i].second;
        int delay = crackdown[i].first;
        for(int r = 1; r <= V; r++){
            for(int c = 1; c <= V; c++){
                Graph[r][c] = min(Graph[r][c], Graph[r][via] + Graph[via][c]);
                res[r][c] = min(res[r][c], Graph[r][via] + delay + Graph[via][c]);
            }
        }
    }
    
    for(int i = 0; i < T; i++){
        cout << res[output[i].first][output[i].second] << "\n";
    }
    
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}