2253:Frogger - komiyamの日記

keyword

概要

2次元平面上に石が置いてある。石から石へジャンプして初期位置から目的位置まで移動したい。このとき最低限必要なジャンプ力を求めよ。
初期位置から目的位置までの最短経路とは別の問題だけど、DPちっくに書こうと思ったらDijkstraっぽくなった。初期位置からその石まで移るのに必要なジャンプ力をpriority_queueを使って順に確定させる。

inline double dist(int x, int y){
    return sqrt(x*x + y*y);
}

int main(){
    double mat[202][202];
    double list[202];
    int i, j, n, cnt=0;
    int xs[202], ys[202];

    while(1){
        scanf("%d",&n);
        if(!n) break;
        REP(i,n)scanf("%d%d",xs+i,ys+i);
        REP(i,n)REP(j,n)mat[i][j] = dist(xs[i]-xs[j], ys[i]-ys[j]);
        REP(i,n) list[i] = 0.0;
        priority_queue< pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > Q;
        Q.push(MP(0.0, 0));
        while(!Q.empty() && list[1]==0.0){
            pair<double, int> tp = Q.top(); Q.pop();
            if(list[tp.sc] == 0.0){
                list[tp.sc] = tp.fs;
                REP(i,n)if(i!=tp.sc){
                    Q.push(MP(max(list[tp.sc], mat[tp.sc][i]), i));
                }
            }
        }
        printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++cnt, list[1]);
    }

    return 0;
}