| ||||||||||
| 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 | |||||||||
G++ WA,C++ TLE,郁闷!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