2253 Frogger

#include<iostream>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<stdio.h>
using namespace std;
typedef pair<int,int> pii;
int T;
const int N =220;
pii vec[N];
bool st[N];
double w[N][N],dst[N];

double dist(pii a,pii b){
    return sqrt((double)((b.second-a.second)*(b.second-a.second)+(b.first-a.first)*(b.first-a.first)));
}

double dijkstra(){
    memset(dst,0x42,sizeof(dst));
    dst[1] = 0;
    
    for(int i=0;i<T-1;i++){
        int t = -1;
        for(int j=1;j<=T;j++){
            if(!st[j]&&(t==-1||dst[j]<dst[t])){
                t = j;
            }
        }
        for(int j =1 ;j<=T;j++){
            dst[j] = min(dst[j],max(dst[t],w[t][j]));   //题目求的是路径中的最大的边
        }
        st[t] = true;
    }
    return dst[2];
    
}

int main(){
    int cnt = 1;
    while(cin>>T,T){
        memset(st,0,sizeof(st));
        for(int i=1;i<=T;i++) cin>>vec[i].first>>vec[i].second; 
        for(int i=1;i<=T;i++){
            for(int j = i;j<=T;j++){
                double c = dist(vec[i],vec[j]);
                w[j][i] = w[i][j] = c;
                //cout<<i<<" "<<j<<" "<<c<<endl;
            }
        }
        double t = dijkstra();
        printf("Scenario #%d\n",cnt);
        printf("Frog Distance = %0.3f\n",t);
        puts("");
        cnt ++;
    }
    return 0;
}