Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

G++ WA,C++ TLE,郁闷!

Posted by 2guangnian at 2010-10-29 16:42:41 on Problem 2502
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator