hdu 4179 Difficult Routes这个问题中为什么我的代码总超时，请问，求大佬帮助，感激不尽！

Question

我的代码和网上代码几乎一样了，就是存储方式不对，可提交总是超时，有大佬帮帮忙看一下吗？请问，找了2天的错误了，一点头绪都没有，求助大佬！

网上代码：

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#define MAXN 10005

#define MAXM 200005

#define LL long long

const double INF=1e16;

const double eps = 1e-10;

int n,m,d;

struct node

{

node(int st=0,int en=0,int next=0,int d=0,double len=0)

{

    this->st=st;

    this->en=en;

    this->next=next;

    this->d=d;

    this->len=len;

}

int st,en,next,d;

double len;

};

struct node E[MAXM],e[MAXM];//声明存边数组（正向边和方向边）

struct point

{

long long int x,y,z;

}po[MAXN];

double dis1[MAXN],dis2[MAXN];

int vis[MAXN];

int p[MAXN],num,numf,pp[MAXN];

double abss(double x)

{

if(x<0)

    return -x;

return x;

}

double min(double x,double y)

{

return x<y?x:y;

}

double length(point p1,point p2)

{

double ans;

ans=(p1.x-p2.x)*(p1.x-p2.x);

ans+=(p1.y-p2.y)*(p1.y-p2.y);

ans+=(p1.z-p2.z)*(p1.z-p2.z);

ans=sqrt(ans);

return  ans;

}

double length1(point p1,point p2)

{

double ans;

ans=(p1.x-p2.x)*(p1.x-p2.x);

ans+=(p1.y-p2.y)*(p1.y-p2.y);

ans=sqrt(ans);

return  ans;

}

int level(point p1,point p2)

{

if(p1.z>=p2.z)

    return 0;

double len=length1(p1,p2);

double high=abss(p1.z-p2.z);

int ans=(int)((high/len)*100.0);



return ans;

}

void add(int st,int en)

{

E[num].st=st;

E[num].en=en;

E[num].next=p[st];

E[num].len=length(po[st],po[en]);

//cout<"<<en<<" d:"<<E[num].d<<" len:"<<E[num].len<<endl;

p[st]=num++;

}

void ADD(int st,int en)

{

e[numf].st=st;

e[numf].en=en;

e[numf].next=pp[st];

e[numf].len=length(po[st],po[en]);

pp[st]=numf++;

}

void spfa(int st,double *dis,struct node *ee,int *P)

{

int i;

queue<int>q;

for(i=0;i<MAXN;i++)

      dis[i]=INF;

dis[st]=0;

memset(vis,0,sizeof(vis));

q.push(st);

vis[st]=1;

while(!q.empty())

{

    int tx=q.front();

    q.pop();

    vis[tx]=0;

    for(i=P[tx];i!=-1;i=ee[i].next)

    {

        int enn=ee[i].en;

        double len=ee[i].len;

        if(dis[enn]>dis[tx]+len)

        {



            dis[enn]=dis[tx]+len;

            if(!vis[enn])

            {

                vis[enn]=1;

                q.push(enn);

            }

        }

    }

}

}

int u[MAXM],v[MAXM],a[MAXM],cnt;

int main()

{

int i;

while(scanf("%d%d",&n,&m)!=EOF)

{

    if(n==0&&m==0)break;

    memset(p,-1,sizeof(p));

    num=0;

    numf=0;

    memset(pp,-1,sizeof(pp));

    for(i=1;i<=n;i++)

    {

        scanf("%lld%lld%lld",&po[i].x,&po[i].y,&po[i].z);

    }



    for(i=1;i<=m;i++)

    {

        scanf("%d%d",&u[i],&v[i]);

    }

    int st,en;

    scanf("%d%d%d",&st,&en,&d);

    cnt=0;

    for(i=1;i<=m;i++)

    {

        int dd=level(po[u[i]],po[v[i]]);

        if(dd<=d)

        {

            add(u[i],v[i]);//正向

            ADD(v[i],u[i]);//反向边

        }

        if(dd==d) a[++cnt]=num-1;//存正好难度为d的边的编号



        dd=level(po[v[i]],po[u[i]]);

        if(dd<=d)

        {

            add(v[i],u[i]);

            ADD(u[i],v[i]);//反向边

        }

        if(dd==d) a[++cnt]=num-1;

    }

    spfa(st,dis1,E,p);

    spfa(en,dis2,e,pp);

    double minx=INF;

    for(i=1;i<=cnt;i++)

    {

        int numm=a[i];

        int qi=E[numm].st,zhong=E[numm].en;

        double temp=E[numm].len;

        temp+=dis1[qi]+dis2[zhong];

        if(minx>temp)

            minx=temp;

    }



    if(minx!=INF)

    printf("%.1lf\n",minx);

    else puts("None");

}

return 0;

}

我的代码：

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;
const double INF = 1e16;
struct point
{
long long int x;
long long int y;
long long int z;
}dian[20010];
struct edge
{
int pre;
double w;
int to;
int next;
int n;
} e[200100],E[20010];
int bian=0,head[20010],n,d,bian2,head2[20010],ques,ques2;
double leng(point a,point b)
{
long long int x=(a.x-b.x)*(a.x-b.x);
//printf("x=%lld",x);
long long int y=(a.y-b.y)*(a.y-b.y);
// printf("y=%lld",y);
long long int z=(a.z-b.z)*(a.z-b.z);
//printf("z=%lld\n",z);
double cc=sqrt((x+y+z)*1.0);
//printf("cc=%lf\n",cc);
return cc;
}
double leng2(point a,point b)
{
long long x=(a.x-b.x)*(a.x-b.x);
long long y=(a.y-b.y)*(a.y-b.y);
double cc= sqrt(x+y);
return cc;
}
int level(point a,point b)
{
if(a.z>=b.z)
return 0;
long long t=(b.z-a.z)*100;
// printf("t=%ld\n",t);
double le=leng2(a,b);
//printf("le=%lf\n",le);
int cc= (int)((t*1.0/le));
// printf("cc=%d\n",cc);
return cc;
}
void add(int x,int y,double w,int n)
{
bian++;
// printf("bian=%d\n",bian);
e[bian].pre=x;
e[bian].next=head[x];
head[x]=bian;
e[bian].to=y;
e[bian].w=w;
e[bian].n=n;

}
void ADD(int x,int y,double w,int n)
{
bian2++;
E[bian2].pre=x;
E[bian2].next=head2[x];
head2[x]=bian2;
E[bian2].to=y;
E[bian2].w=w;
E[bian2].n=n;
}
void spfa(int x,double* Uh,edge* e3,int *he)
{
int en[20010]={0};
for(int i=1;i<=n;i++)
Uh[i]=INF;
Uh[x]=0;
en[x]=1;
queueq;
q.push(x);
while(!q.empty())
{
int c=q.front();
q.pop();
en[c]=0;
for(int i=he[c];i!=-1;i=e3[i].next)
{
int y=e3[i].to;

            if(Uh[y]>Uh[c]+e3[i].w)
            {
                Uh[y]=Uh[c]+e3[i].w;
                if(!en[y])
                {
                    en[y]=1;
                    q.push(y);
                }
            }

    }
}

}

int an[200010]={0},bn[200010]={0};
double sh[20010];
double ch[20010];
int main()
{
int m;
while(scanf("%d%d",&n,&m)!=EOF)
{

if(n==0&&m==0)
return 0;



    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&dian[i].x,&dian[i].y,&dian[i].z);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",an+i,bn+i);

    }

    memset(head,-1,sizeof(head));
    memset(head2,-1,sizeof(head2));
    bian=bian2=0;
    int th[200100]={0},rr=0;
    int t,tt;
    scanf("%d%d%d",&t,&tt,&d);

    for(int i=1;i<=m;i++)
    {
        int a1=an[i],b1=bn[i];
          double len;
          len=leng(dian[a1],dian[b1]);

          ques=level(dian[a1],dian[b1]);

          if(ques<=d)
          {
            //printf("   quesques=%d\n",ques);
            //printf("ques=%d,",ques);
            add(a1,b1,len,ques);
            if(ques==d)
            th[++rr]=bian;
            ADD(b1,a1,len,ques);
          }
           ques2=level(dian[b1],dian[a1]);
           //   printf("...d=%d,ques2=%d\n",d,ques2);
          // printf("....i=%d,jigu=%d\n",i,ques2);
          if(ques2<=d)
          {

            add(b1,a1,len,ques2);
          //    printf("d=%d,ques2=%d,bian=%d\n",d,ques2,bian);
            if(ques2==d)
            {
                rr++;
                th[rr]=bian;
            }
            ADD(a1,b1,len,ques2);
          }


    }
    for(int i=1;i<=rr;i++)
    spfa(tt,sh,E,head2);
    spfa(t,ch,e,head);
    double mi=INF；
    for(int j=1;j<=rr;j++)
    {
        int i=th[j];
            double u=ch[e[i].pre];
            double uu= sh[e[i].to];
            double g=u+uu+e[i].w;
            if(mi>g)
            mi=g;

    }
    if(mi<INF)
    printf("%.1lf\n",mi);
    else
    printf("None\n");

}
return 0;
}

hdu题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4179

题目也可以看：https://blog.csdn.net/swust_lian/article/details/50523040，我找的代码就是这个博客大佬