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 |
应该是数组开小了,最多200个stop,还要加上家和学校,201确实小了In Reply To:谁能告诉我为什么我的Dijkstra TLE了。。。十分感谢 Posted by:2guangnian at 2010-10-29 16:30:03 > #include<iostream> > #include<cmath> > #include<algorithm> > #define inf 9999999.9 > double x[201],y[201],g[201][201],dis[201]; > int u[201],cnt; > int main() > { > int i,j,k,flag; > double a,b,min,temp; > scanf("%lf%lf%lf%lf",&x[1],&y[1],&x[2],&y[2]); > cnt=3; > while(scanf("%lf%lf",&a,&b)!=EOF) > { > if(a==-1&&b==-1) > { > continue; > } > if(a==-2&&b==-2) > break; > x[cnt]=a; > y[cnt]=b; > cnt++; } > for(i=1;i<cnt;i++) > for(j=1;j<cnt;j++) > { > if(i==j||g[i][j]!=0.0) > continue; > else if(y[i]==y[j]) > g[i][j]=g[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))/40000.0; > else > g[i][j]=g[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))/10000.0; > } > u[1]=1; > for(i=1;i<cnt;i++) > dis[i]=g[1][i]; > for(i=1;i<cnt;i++) > { > min=inf; > for(j=1;j<cnt;j++) > { > if(!u[j]&&dis[j]<min) > { > min=dis[j]; > k=j; > } > } > u[k]=1; > for(j=1;j<cnt;j++) > { > if(dis[j]>dis[k]+g[k][j]) > dis[j]=dis[k]+g[k][j]; > } > } > printf("%d\n",(int)(60.0*dis[2])); > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator