#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=1005;
vector<pair<int,double> >E[maxn];
double x[maxn],y[maxn];
double d[maxn];
double maps[maxn][maxn];

void init()
{
    for(int i=0;i<maxn;i++)E[i].clear();
    for(int i=0;i<maxn;i++)d[i]=1e9;
        //for(int j=0;j<maxn;j++)
            //d[i][j]=1e9;
}

int main()
{
    int t,temp=1;
    while(~scanf("%d",&t))
    {
        if(t==0)
            break;
        init();
        for(int i=1;i<=t;i++)
        {
            scanf("%lf%lf",&x[i],&y[i]);
        }

        for(int i=1;i<=t;i++)
        {
            for(int j=1;j<=t;j++)
            {
                //if(i==j)continue;
                maps[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                E[i].push_back(make_pair(j,maps[i][j]));
                E[j].push_back(make_pair(i,maps[i][j]));
            }
        }
        /*for(int i=1;i<=3;i++)
        {
            for(int j=0;j<=5;j++)
            {
                cout<<E[i][j].second<<" ";
            }
            cout<<endl;
        }*/
        //printf("%.3lf",E[1][3].second);
        priority_queue<pair<double,int> >Q;
        Q.push(make_pair(-d[1],1));
        d[1]=0;
        while(!Q.empty())
        {
            int now=Q.top().second;
            Q.pop();
            for(int i=0;i<E[now].size();i++)
            {
                int v=E[now][i].first;
                if(d[v]>d[now]&&d[v]>E[now][i].second)
                {
                    /*if(d[now]>E[now][i].second)
                    {
                        d[v]=d[now];
                    }
                    else if(d[now]<E[now][i].second)
                    {
                        d[v]=E[now][i].second;
                    }*/
                    d[v]=max(d[now],E[now][i].second);
                    Q.push(make_pair(-d[v],v));
                }
            }
        }
        printf("Scenario #%d\nFrog Distance = %.3f \n\n",temp++,d[2]);

    }
}

• 找到BUG了...啦啦啦 (53) tenglinxi 2016-05-24 21:18:08