1 //Accepted    468 KB    16 ms 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <queue> 6 #include <cmath> 7 #include <algorithm> 8 using namespace std; 9 /**10   * This is a documentation comment block11   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！12   * @authr songt13   */14 const int imax_n = 205;15 const int inf = 100000000;16 int x[imax_n];17 int y[imax_n];18 double a[imax_n][imax_n];19 bool vis[imax_n];20 double dis[imax_n];21 int n;22 double max(double a,double b)23 {24     if (a-b<1e-9) return b;25     return a;26 }27 double min(double a,double b)28 {29     if (a-b>1e-9) return b;30     return a;31 }32 void dij(int src)33 {34     memset(vis,false,sizeof(vis));35     vis[src]=true;36     for (int i=1;i<=n;i++)37     dis[i]=a[src][i];38     for (int i=1;i<=n;i++)39     {40         double temp=inf;41         int k=-1;42         for (int j=1;j<=n;j++)43         {44             if (vis[j]) continue;45             if (temp-dis[j]>1e-9)46             {47                 temp=dis[j];48                 k=j;49             }50         }51         if (k==-1) return ;52         vis[k]=true;53         for (int j=1;j<=n;j++)54         if (!vis[j])55         {56             dis[j]=min(dis[j],max(dis[k],a[k][j]));57         }58     }59 }60 int main()61 {62     int t=0;63     while (scanf("%d",&n),n)64     {65         for (int i=1;i<=n;i++)66         {67             scanf("%d%d",&x[i],&y[i]);68         }69         for (int i=1;i<=n;i++)70         {71             for (int j=1;j<=n;j++)72             a[i][j]=sqrt((double )(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));73         }74         dij(1);75         printf("Scenario #%d\nFrog Distance = %.3lf\n\n",++t,dis[2]+0.000005);76     }77     return 0;78 }