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

``````
``````
``````
``````

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

}

{

``````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++;
``````

}

{

``````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)

{

}

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

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

if(dd<=d)

{

}

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];
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].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].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);

}

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);
if(ques==d)
th[++rr]=bian;
}
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)
{

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

}
for(int i=1;i<=rr;i++)
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;
}

``````
``````
``````
``````
``````
``````