| ||||||||||
| 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 | |||||||||
水题一道!dijkstra松弛技术无压力,注意%.3f和%.3lf!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#include <cstdio>
#include <cmath>
#define __max(a,b) ((a)>(b)?(a):(b))
#define __min(a,b) ((a)<(b)?(a):(b))
#define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
float x[222],y[222];
float dis(int a,int b){
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
int n;
bool vst[222];
float d[222];
void dijkstra(){
rep(i,0,n){
d[i]=10000000;
vst[i]=0;
}
d[0]=0;
rep(i,0,n){
int mind=9999999,mink;
rep(j,0,n)
if(!vst[j]&&mind>d[j]){
mind=d[j];
mink=j;
}
vst[mink]=1;
rep(j,0,n)d[j]=__min(d[j],__max(d[mink],dis(mink,j)));
}
}
int main(){
int cas=0;
while(scanf("%d",&n)&&n){
rep(i,0,n)scanf("%f%f",x+i,y+i);
dijkstra();
printf("Scenario #%d\nFrog Distance = %.3f\n\n",++cas,d[1]);//POJ 用%.f过
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator