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