POJ 2253 Frogger

この問題は石1から石2までの最長ジャンプ距離の最小値を要求し,最適化されたdijを積み上げて作ったが,意外によいとは思わなかった.
長い間最短を書いていないので,これは全部うまく書けなくなった.floydで任意の2つの石の間の距離を求めることもできます.つまり
ジャンプ距離を指定し、1～2の最長パスの最小値を指定します.

/*Accepted    636K    0MS    C++    1453B    2012-07-26 11:51:06*/

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<queue>

#include<cmath>

#include<iostream>

using namespace std;



typedef pair< double,int > pii;

const int MAXN = 1 << 8;

double x[MAXN], y[MAXN] ;

double g[MAXN][MAXN] ;

int n;



double dis( double a, double b)

{

    return sqrt(a * a + b * b);

}



void ReadGragh()

{

    for( int i = 1; i <= n; i ++)

        scanf( "%lf%lf", &x[i], &y[i]);

    for( int i = 1; i <= n; i ++)

        for( int j = i; j <= n; j ++)

        {

            g[i][j] = g[j][i] = dis( x[i] - x[j], y[i] - y[j]);

        }

}



double Dijkstra()

{

    priority_queue< pii, vector<pii>, greater<pii> > q;

    double dist[MAXN] = {0.0};

    for( int i = 2; i <= n; i ++)

        dist[i] = 1e120;

    q.push( make_pair(0.0, 1));

    while( !q.empty())

    {

        pii u = q.top(); q.pop();

        int x = u.second;

        if( x == 2) return dist[2];

        if( dist[x] != u.first) continue; //        

        for( int i = 2; i <= n; i ++)

        {

            if( i != x && dist[i] > max(dist[x], g[x][i]) )

            {

                dist[i] = max(dist[x], g[x][i]);

                q.push( make_pair(dist[i], i));

            }

        }

    }

    return 0;

}



int main()

{

    int cas = 1;

    while( scanf("%d", &n), n)

    {

        ReadGragh();

        printf( "Scenario #%d
", cas ++);

        printf( "Frog Distance = %.3f

", Dijkstra());

    }

}