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

Re:大侠看看呀。。为何过不了啊。。thx+++

Posted by yuech at 2009-12-13 02:56:19 on Problem 2502
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:
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