1 /*  2    题意：就是源点到终点有多条的路径，每一条路径中都有一段最大的距离！  3     求这些路径中最大距离的最小值！  4       5    Dijkstra, Floyd, spfa都是可以的！只不过是将松弛的条件变一下就行了！  6   7    想了一下，这道题用最小生成树做也可以啊，图总是连通的嘛!所以建一棵最小  8    生成树，然后dfs一下，从源点1，到终点2的路径上，查找边长最大的路径！   9    附上代码.....  10 */ 11 #include<iostream> 12 #include<cstdio> 13 #include<algorithm> 14 #include<cstring> 15 #include<cmath> 16 #include<iomanip> 17 #define INF 0x3f3f3f3f*1.0 18 using namespace std; 19 struct node{ 20     double x, y;        21 }; 22 node nd[205]; 23 double g[205][205]; 24 double d[205]; 25 int vis[205]; 26 int n; 27  28 void Dijkstra(){  29    memset(vis, 0, sizeof(vis)); 30    d[1]=0.0; 31    int root=1; 32    vis[1]=1; 33    for(int i=2; i<=n; ++i) 34       d[i]=INF; 35    for(int j=1; j<n; ++j){ 36        int p; 37        double minL=INF; 38        for(int i=1; i<=n; ++i){ 39           double dist; 40           if(!vis[i] && d[i]> (dist=max(d[root], g[root][i]))) 41               d[i]=dist; 42           if(!vis[i] && minL>d[i]){ 43               minL=d[i]; 44               p=i;            45           } 46        } 47        if(minL==INF) return; 48        root=p; 49        vis[root]=1; 50    } 51 } 52  53 int main(){ 54    int cnt=0; 55    while(cin>>n && n){ 56        for(int i=1; i<=n; ++i) 57           for(int j=1; j<=n; ++j) 58              g[i][j]=INF; 59        for(int i=1; i<=n; ++i){ 60           double u, v; 61           cin>>nd[i].x>>nd[i].y; 62           for(int j=1; j<i; ++j){ 63              u=nd[i].x-nd[j].x;         64              v=nd[i].y-nd[j].y; 65              g[i][j]=g[j][i]=sqrt(u*u + v*v); 66           }         67        } 68        Dijkstra(); 69        cout<<"Scenario #"<<++cnt<<endl<<"Frog Distance = "; 70        cout<<fixed<<setprecision(3)<<d[2]<<endl; 71        cout<<endl; 72    } 73    return 0;     74 } 75  76 //最小生成树思想 77 #include<iostream> 78 #include<cstdio> 79 #include<algorithm> 80 #include<cstring> 81 #include<cmath> 82 #include<iomanip> 83 #define INF 0x3f3f3f3f*1.0 84 using namespace std; 85 struct node{ 86     double x, y;      87 }; 88 node nd[205]; 89  90 struct EDGE{ 91    int u, v; 92    double dist;        93 }; 94 EDGE edge[21000]; 95  96 bool cmp(EDGE a, EDGE b){ 97    return a.dist < b.dist;      98 } 99 100 double g[205][205];101 102 int vis[205], f[205];103 int n;104 105 int getFather(int x){106    return x==f[x] ? x : f[x]=getFather(f[x]);    107 }108 109 bool Union(int a, int b){110      int fa=getFather(a), fb=getFather(b);111      if(fa!=fb){112          f[fa]=fb;113          return true;           114      } 115      return false;116 }117 double dd;118 bool dfs(int cur, double ddd){119     vis[cur]=1;120     if(cur==2){121        dd=ddd;122        return true;           123     }124     for(int i=1; i<=n; ++i)125        if(g[cur][i]!=INF && !vis[i]){126             if(ddd<g[cur][i]){127                if(dfs(i, g[cur][i]))  return true;128             }129             else if(dfs(i, ddd)) return true;           130        } 131     return false;    132 }133 134 int main(){135    int cnt=0;136    while(cin>>n && n){137        for(int i=1; i<=n; ++i)138           for(int j=1; j<=n; ++j)139              g[i][j]=INF;140        int count=0;141        for(int i=1; i<=n; ++i){142           double u, v;143           cin>>nd[i].x>>nd[i].y;144           for(int j=1; j<i; ++j){145              u=nd[i].x-nd[j].x;        146              v=nd[i].y-nd[j].y;147              edge[count].u=i;148              edge[count].v=j;149              edge[count++].dist=sqrt(u*u + v*v);150           }        151        }152        sort(edge, edge+count, cmp);153        for(int i=1; i<=n; ++i)154           f[i]=i;155        for(int i=0; i<count; ++i){156            int u, v;157            if(Union(u=edge[i].u, v=edge[i].v))158               g[u][v]=g[v][u]=edge[i].dist;        159        }160        memset(vis, 0, sizeof(vis));161        dfs(1, 0.0);162        cout<<"Scenario #"<<++cnt<<endl<<"Frog Distance = ";163        cout<<fixed<<setprecision(3)<<dd<<endl;164        cout<<endl;165    }166    return 0;    167 }