| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这道题目flody就可以过了不用写dijstra和spfa算法附代码给大家!!!如有雷同我就去死!#include <stdio.h>
#include <string.h>
#include <math.h>
#define len 210
#define MAX 100000000
double max(double a,double b)
{
if(a>b)
return a;
else
return b;
}
double min(double a,double b)
{
if(a>b)
return b;
else
return a;
}
double road[len][len];
typedef struct node
{
double x;
double y;
}Node;
Node point[len];
int n,times;
void flody()
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
road[i][j]=min(road[i][j],max(road[i][k],road[k][j]));
}
}
printf("Scenario #%d\n",times++);
printf("Frog Distance = %.3lf\n",road[1][2]);
printf("\n");
}
int main()
{
int i,j,k;
double d;
times=1;
while(scanf("%d",&n)!=EOF&&n)
{
getchar();
for(k=1;k<=n;k++)
scanf("%lf %lf",&point[k].x,&point[k].y);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
road[i][j]=MAX;
road[i][i]=0;
}
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++)
{
d=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));
road[i][j]=d;
road[j][i]=d;
}
}
/*
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%lf ",road[i][j]);
printf("\n");
}
*/
flody();
}
return 1;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator