dijkstra變種
wa了3次..
pe一次
另外orz一下樣例...太完美了..對我做題沒任何幫助
#include <iostream>
#include <math.h>
using namespace std;
struct node
{
int x,y;
};
const int MAXN=201;
node point[MAXN];
double dist[MAXN];
double answer[MAXN];
bool hash[MAXN];
int n;
inline double distances(int u,int v)
{
double value=(point[u].x-point[v].x)*(point[u].x-point[v].x)+(point[u].y-point[v].y)*(point[u].y-point[v].y);
return sqrt(value);
}
double max(double x,double y)
{
return x>y?x:y;
}
int main()
{
int num=0;
while(1)
{
cin>>n;
if (0==n) break;
for (int i=1;i<=n;i++)
{
cin>>point[i].x>>point[i].y;
}
memset(dist,0x7f,sizeof(dist));
memset(answer,0x7f,sizeof(dist));
memset(hash,0,sizeof(hash));
dist[1]=0.0f;
answer[1]=0.0f;
for (int i=1;i<=n;i++)
dist[i]=distances(1,i);
for (int i=1;i<n;i++)
{
int u=0;
double min=0x7fffffff;
for (int j=1;j<=n;j++)
{
if (hash[j]) continue;
if (min>dist[j]) {min=dist[j];u=j;}
}
hash[u]=true;
if (0==u) break;
for (int j=1;j<=n;j++)
{
{
if (dist[j]>max(dist[u],distances(u,j))) dist[j]=max(dist[u],distances(u,j));
}
}
}
printf("%s%d\n","Scenario #",++num);
printf("%s%.3f\n\n","Frog Distance = ",dist[2]);
}
return 0;
}