题目链接:http://poj.org/problem?id=2253
就是求所有路径的最大边权值的最小值
处理时每次找出距离当前的已选的节点的最短距离,然后更新每个未选节点的值
代码:
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define maxn 210
#define INF 1010101010
int n;
double G[maxn][maxn];
double dis[maxn];
int s[maxn];
class point
{
public:
double x;
double y;
};
point p[maxn];
double dist( point a ,point b)
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void Dijkstra()
{ for(int i=;i<=n;i++)
{
dis[i]=G[][i];
s[i]=;
}
s[]=; for(int i=;i<n;i++)
{
int Min=INF;
int u=-;
for(int j=;j<=n;j++)
{
if(s[j]== && dis[j]<Min)
{
Min=dis[j];
u=j;
}
}
if(u==-) break;
s[u]=;
for(int i=;i<=n;i++)
{
if(s[i]== && max(dis[u],G[u][i])<dis[i])
dis[i]=max(dis[u],G[u][i]);
}
}
}
int main()
{
int iCase=;
while(scanf("%d",&n)!=EOF && n)
{ for(int i=;i<=n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
G[i][j]=G[j][i]=dist(p[i],p[j]);
} Dijkstra();
cout<<"Scenario #"<<++iCase<<endl;
printf("Frog Distance = %.3f\n\n",dis[]); }
}