#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;
}

• Re:大侠看看呀。。为何过不了啊。。thx+++ (2760) yuech 2009-12-13 02:56:19
• Re:大侠看看呀。。为何过不了啊。。thx+++ (306) yuech 2009-12-13 02:58:09