/*
题意:就是源点到终点有多条的路径,每一条路径中都有一段最大的距离!
求这些路径中最大距离的最小值! Dijkstra, Floyd, spfa都是可以的!只不过是将松弛的条件变一下就行了! 想了一下,这道题用最小生成树做也可以啊,图总是连通的嘛!所以建一棵最小
生成树,然后dfs一下,从源点1,到终点2的路径上,查找边长最大的路径!
附上代码.....
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#define INF 0x3f3f3f3f*1.0
using namespace std;
struct node{
double x, y;
};
node nd[];
double g[][];
double d[];
int vis[];
int n; void Dijkstra(){
memset(vis, , sizeof(vis));
d[]=0.0;
int root=;
vis[]=;
for(int i=; i<=n; ++i)
d[i]=INF;
for(int j=; j<n; ++j){
int p;
double minL=INF;
for(int i=; i<=n; ++i){
double dist;
if(!vis[i] && d[i]> (dist=max(d[root], g[root][i])))
d[i]=dist;
if(!vis[i] && minL>d[i]){
minL=d[i];
p=i;
}
}
if(minL==INF) return;
root=p;
vis[root]=;
}
} int main(){
int cnt=;
while(cin>>n && n){
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j)
g[i][j]=INF;
for(int i=; i<=n; ++i){
double u, v;
cin>>nd[i].x>>nd[i].y;
for(int j=; j<i; ++j){
u=nd[i].x-nd[j].x;
v=nd[i].y-nd[j].y;
g[i][j]=g[j][i]=sqrt(u*u + v*v);
}
}
Dijkstra();
cout<<"Scenario #"<<++cnt<<endl<<"Frog Distance = ";
cout<<fixed<<setprecision()<<d[]<<endl;
cout<<endl;
}
return ;
} //最小生成树思想
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#define INF 0x3f3f3f3f*1.0
using namespace std;
struct node{
double x, y;
};
node nd[]; struct EDGE{
int u, v;
double dist;
};
EDGE edge[]; bool cmp(EDGE a, EDGE b){
return a.dist < b.dist;
} double g[][]; int vis[], f[];
int n; int getFather(int x){
return x==f[x] ? x : f[x]=getFather(f[x]);
} bool Union(int a, int b){
int fa=getFather(a), fb=getFather(b);
if(fa!=fb){
f[fa]=fb;
return true;
}
return false;
}
double dd;
bool dfs(int cur, double ddd){
vis[cur]=;
if(cur==){
dd=ddd;
return true;
}
for(int i=; i<=n; ++i)
if(g[cur][i]!=INF && !vis[i]){
if(ddd<g[cur][i]){
if(dfs(i, g[cur][i])) return true;
}
else if(dfs(i, ddd)) return true;
}
return false;
} int main(){
int cnt=;
while(cin>>n && n){
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j)
g[i][j]=INF;
int count=;
for(int i=; i<=n; ++i){
double u, v;
cin>>nd[i].x>>nd[i].y;
for(int j=; j<i; ++j){
u=nd[i].x-nd[j].x;
v=nd[i].y-nd[j].y;
edge[count].u=i;
edge[count].v=j;
edge[count++].dist=sqrt(u*u + v*v);
}
}
sort(edge, edge+count, cmp);
for(int i=; i<=n; ++i)
f[i]=i;
for(int i=; i<count; ++i){
int u, v;
if(Union(u=edge[i].u, v=edge[i].v))
g[u][v]=g[v][u]=edge[i].dist;
}
memset(vis, , sizeof(vis));
dfs(, 0.0);
cout<<"Scenario #"<<++cnt<<endl<<"Frog Distance = ";
cout<<fixed<<setprecision()<<dd<<endl;
cout<<endl;
}
return ;
}