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 |
Re:大侠看看呀。。为何过不了啊。。thx+++In Reply To:大侠看看呀。。为何过不了啊。。thx+++ Posted by:782423381 at 2009-10-20 22:41:06 > #include<stdio.h> > #include<math.h> > #include<string.h> > double x[200+10],y[200+10],x11,x22,y11,y22; > int pos; > const double INF = 100000000000000 ; > double d[200+10][200+10],g[200+10][200+10],dd[200+10]; > inline double dis1(const double &a,const double&b,const double &c,const double &d) > { > return sqrt((a-c)*(a-c)+(b-d)*(b-d))/1000/40*60; > } > inline double dis2(const double &a,const double&b,const double &c,const double &d) > { > return sqrt((a-c)*(a-c)+(b-d)*(b-d))/1000/10*60; > } > /*int floyd( int n) > { > int i,j,k; > for (k =0; k <n; k ++ ) > { > for (i = 0 ; i < n; i ++ ) > for (j = 0 ; j <n; j ++ ) > { > if (d[i][k] < INF && d[k][j] < INF&& d[i][k] + d[k][j] < d[i][j]) > d[i][j] = d[i][k] + d[k][j]; > } > } > printf("%.0f\n",d[0][n-1]); > return 0 ; > }*/ > void Dijkstra(int n,int v,double *Dist) //或int Dist[MAX]; > { > double Cost[200+10][200+10]; > memcpy(Cost,d,sizeof(Cost)); > double temp,newdist; > int i,j,u; > bool s[200+10]; > for(i=0;i<n;i++) Cost[i][i]=0; > for(i=0;i<n;i++) > { > Dist[i]=Cost[v][i]; > s[i]=false; > } > > Dist[v]=0; > s[v]=true; > > for(i=1;i<n;i++) > { > temp=INF; > //u=v; > for(j=0;j<n;j++) > { > if((!s[j]) && (Dist[j]<temp)) > { > u=j; temp=Dist[j]; > } > } > s[u]=true; > for(j=0;j<n;j++) > { > if((!s[j]))// && (Cost[u][j]<MAXVALUE)) > { > newdist=Dist[u]+Cost[u][j]; > if(newdist<Dist[j]) Dist[j]=newdist; > } > } > } > printf("%.0lf",Dist[n-1]); > return ; > } > > void process() > { > int i,j; > double t1,t2; > for(i=0,pos=0;i<200+10;i++) > for(j=0;j<200+10;j++) d[i][j]=INF; > x[pos]=x11,y[pos++]=y11; > while(scanf("%lf%lf",&t1,&t2)==2) > { > if(t1==-1&&t2==-1) continue; > x[pos]=t1,y[pos++]=t2; > while(true) > { > scanf("%lf%lf",&t1,&t2); > if(t1==-1&&t2==-1) break; > x[pos]=t1,y[pos]=t2; > d[pos][pos-1]=d[pos-1][pos]=dis1(x[pos],y[pos],x[pos-1],y[pos-1]); > ++pos; > } > } > x[pos]=x22,y[pos++]=y22; > for(i=0;i<pos;i++) > for(j=i+1;j<pos;j++) > { > double xxx=dis2(x[i],y[i],x[j],y[j]); > if(xxx<d[i][j]) d[i][j]=xxx; > } > // floyd(pos); > Dijkstra(pos,0,dd); > } > int main() > { > //freopen("in.txt","r",stdin); > //freopen("out.txt","w",stdout); > while(scanf("%lf%lf%lf%lf",&x11,&y11,&x22,&y22)==4) process(); > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator