[백준] Roadblock

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

5917번: Roadblock

bfs를 이용하는 문제입니다.

 

문제부터 간단하게 요약해보면, 농부가 field를 돌아다니게 되는데, 농부는 매일 최단 경로를 거쳐 헛간으로 갑니다. 소들은 field들을 연결하는 경로중 한 경로를 두배하여 농부가 최대한 늦게 헛간에 도착하게 만드려고 합니다. 이 때, 얼마의 경로차이를 최대로 만들 수 있는지를 return해야 합니다.

 

문제를 실제로 한번 읽어보는 것을 추천합니다.

 

<Solution>

최단경로를 구하는 bfs를 한 다음, 농부가 처음 최단 경로로 갔을 때 이용된 도로를 2배시켜서 각각에 대해 다시 최단경로를 구해봅니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <queue>
#include <algorithm>
#define INF 1<<30

using namespace std;

int N, M;
int roads[101][101];
int path[101];
int cost[101];

void getinput(){
    cin >> N >> M;
    for (int i = 0; i<M; i++){
        int a, b, l;
        cin >> a >> b>>l;
        roads[a][b] = (roads[a][b] == 0)? l : min(roads[a][b], l);
        roads[b][a] = (roads[b][a] == 0)? l : min(roads[b][a], l);
    }
}
int find_short_path(){
    // initialize path, cost array
    for(int i = 0; i<101; i++){
        path[i] = 0;
        cost[i] = INF;
    }

    queue <int> q;

    path[1] = 0;
    cost[1] = 0;
    q.push(1);

    while(!q.empty()){
        int cur = q.front(); q.pop();

        for(int i = 1; i<=N; i++){
            if(cur == i) continue;
            if(roads[cur][i] == 0) continue;

            int new_cost = cost[cur]+roads[cur][i];
            if(new_cost < cost[i]){
                path[i] = cur;
                cost[i] = new_cost;
                q.push(i);
            }
        }
    }
    return cost[N];
}
int solution(){

    int before_short_path = find_short_path();
    // copy path array
    int local_path[101];
    copy(path, path+101, local_path);

    int after_short_path = 0;
    // find path
    int dest = N;
    while(1){
        int src = local_path[dest];
        if(src == 0) break;

        roads[src][dest] = roads[dest][src]*=2;
        after_short_path = max(after_short_path, find_short_path());
        roads[src][dest] = roads[dest][src]/=2;
        dest = src;
    }

    return after_short_path - before_short_path;
}


int main(){
    getinput();

    int ans = solution();

    cout << ans << endl;

}