BOJ 13141. Ignition

문제 링크

 

문제 풀이

 이 문제는 정점의 개수 $N \leq 200$ 이고 간선의 개수 $M \leq 20000$ 인 그래프에서 특정한 정점에 불을 붙여 모든 정점과 모든 간선이 불에 탈 때까지 걸리는 최소시간을 출력하는 문제이다. 어떤 정점에 불이 붙으면  그와 연결된 모든 간선으로 불이 퍼져나간다. 이때 이 간선이 모두 불타는데 걸리는 시간은 그 간선의 길이와 같다. 또한 간선의 양쪽 정점에 모두 불이 붙은 경우는 두 불이 퍼져나가다 만나면 그 간선이 모두 불탄 것이다. 참고로 간선 중에는 양 끝 점이 모두 동일하게 한 정점인 간선도 있다.

 

 처음 한 생각은 일단 모든 정점으로부터 모든 정점까지 최소 거리를 저장하는 것이다. 그렇게 되면 어떤 정점으로부터 불이 시작될 때 어떤 간선이 불에 타서 없어질 때까지 걸리는 시간을 쉽게 계산할 수 있기 때문이다.  $N \leq 200$이므로 $O(N^3)$인 Floyd-Warshall을 사용해서 최소 거리들을 저장해주었다. 그리고 양 끝 점이 동일한 간선의 경우는 따로 저장해주었다.

 

  어떤 간선의 길이가 $L$이고 양 끝점이 $v$와 $u$라고 하자. 그리고 $v$와 $u$는 각각 기준 정점으로부터의 최소 거리가 $x$,$y$라고 하자. $($w.l.o.g. $x \geq y$$)$  만약 $y + L \leq x$ 라면 v에 불이 붙기도 전에 간선이 불에 타 없어지기 때문에 이 간선이 불 탈 때까지 걸리는 시간은 $y + L$이 된다. 만약 $y + L > x$ 라면 $u$로 부터 $x-y$ 간 지점까지 불이 붙고 이후부터는 양쪽에서 불이 오므로 전체 시간은 $x+\frac{L - x + y}{2} = \frac{L+x+y}{2}$이다. 추가적으로 양 끝 점이 동일한 점일 경우는 기준점으로부터의 거리를 $x$라고 할 때 $x + \frac{L}{2}$이다.

 

 따라서 어떤 기준점 $S$에 불을 붙였을 때의 모든 그래프가 불에 탈 때까지 걸리는 시간은 이런 방식으로 계산한 것 중에 최댓값이고, 모든 점들 중의 최댓값중 가장 작은 것을 출력해주면 된다.

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX = 200;
const double INF = 100000000.0;

struct edge{
    double S,E;
    double L;
};

int N,M;
double dist[NMAX+1][NMAX+1];
vector<edge> edges;
vector<edge> cycEdges;

void input(){
    cin>>N>>M;
    
    for(int v=1;v<=N;v++){
        for(int u=1;u<=N;u++){
            if(v == u) continue;
            dist[v][u] = INF;
        }
    }
    
    for(int i=0;i<M;i++){
        int s,e,l;
        cin>>s>>e>>l;
        edge E = {(double)s,(double)e,(double)l};
        if(s == e){
            cycEdges.push_back(E);
            continue;
        }
        edges.push_back(E);
        dist[s][e] == 0 ? (dist[s][e] = (double)l):(dist[s][e] = min((double)l,dist[s][e]));
        dist[e][s] == 0 ? (dist[e][s] = (double)l):(dist[e][s] = min((double)l,dist[e][s]));
    }
}

void floyd(){
    for(int k=1;k<=N;k++){
        for(int v=1;v<=N;v++){
            for(int u=1;u<=N;u++){
                double nd = dist[v][k] + dist[k][u];
                dist[v][u] = min(dist[v][u],nd);
            }
        }
    }
}

double getTime(int st){
    double mxTime = 0.0;
    for(int i=0;i<edges.size();i++){
        double s = edges[i].S;
        double e = edges[i].E;
        double l = edges[i].L;
        double mx = max(dist[st][(int)s],dist[st][(int)e]);
        double mn = min(dist[st][(int)s],dist[st][(int)e]);
        if(mn + l < mx){
            mxTime = max(mxTime, mn + l);
        } else {
            double Time = mx + (l - mx + mn)/2;
            mxTime = max(mxTime, Time);
        }
    }
    for(int i=0;i<cycEdges.size();i++){
        double s = cycEdges[i].S;
        double l = cycEdges[i].L;
        mxTime = max(mxTime,dist[st][(int)s]+l/2);
    }
    return mxTime;
}

void solve(){
    double minTime = INF;
    for(int S=1;S<=N;S++){
        minTime = min(minTime,getTime(S));
    }
    cout.precision(1);
    cout<<fixed<<minTime;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    input();
    floyd();
    solve();
}