SPFA时点出队后一定要把在队内的标记置为false！SPFA时点出队后一定要把在队内的标记置为false！SPFA时点出队后一定要把在队内的标记置为false！
我因为这个卡了一个月大家信吗？测得时候总是60分，丢情况，总之我太弱了
一个月前傻傻的手写堆o(>﹏<)o，现在写Yveh教的我的stl大法的优先队列用于A*爽的飞起(≧▽≦)/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int point[5003],next[200003],v[200003],point2[5003],next2[200003],v2[200003],cnt=0,cnt2=0,N,M;
double c[200003],c2[200003],dist[5003],E;
bool p[5003];
struct datatype{
double g; int isk;
bool operator < (const datatype &a) const
{
return g+dist[isk]>a.g+dist[a.isk];
}
};
void insect(int x,int y,double z){next[cnt]=point[x];point[x]=cnt;v[cnt]=y;c[cnt]=z;cnt++;}
void insect2(int x,int y,double z){next2[cnt2]=point2[x];point2[x]=cnt2;v2[cnt2]=y;c2[cnt2]=z;cnt2++;}
void SPFA()
{
p[N]=1; queue<int>Q;Q.push(N); dist[N]=0.0; int i,now;
while (!Q.empty())
{
now=Q.front(); Q.pop(); p[now]=0;
for (i=point2[now];i!=-1;i=next2[i])
if (dist[v2[i]]>dist[now]+c2[i])
{dist[v2[i]]=dist[now]+c2[i];if (p[v2[i]]==0){p[v2[i]]=1;Q.push(v2[i]);}}
}
}
void Astar()
{
priority_queue<datatype>q; cnt=0;
int i,now; double nowg; datatype A; A.g=0.0; A.isk=1; q.push(A);
while ((E>0)&&(!q.empty()))
{
now=q.top().isk; nowg=q.top().g; q.pop();
if (now==N)
{E=E-nowg; if (E>=0) {cnt++;continue;} else break;}
for (i=point[now];i!=-1;i=next[i])
{A.isk=v[i];A.g=nowg+c[i];q.push(A);}
}printf("%d
",cnt);
}
int main()
{
memset(point,-1,sizeof(point));
memset(point2,-1,sizeof(point2));
memset(next,-1,sizeof(next));
memset(next2,-1,sizeof(next2));
memset(v,0,sizeof(v));
memset(v2,0,sizeof(v2));
memset(c,0,sizeof(c));
memset(c2,0,sizeof(c2));
memset(dist,0x43,sizeof(dist));
memset(p,0,sizeof(p));
scanf("%d %d %lf
",&N,&M,&E);
int i,x,y; double z;
for (i=1;i<=M;++i)
{
scanf("%d %d %lf
",&x,&y,&z);
insect(x,y,z);
insect2(y,x,z);
}SPFA();
Astar();
return 0;
}
2016-03-14：改了改之前的手写堆，在codevs上比stl快多了，，，charge呵呵一笑：stl垃圾(内存我懒得改了，，，codevs上A了就行)
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int duin,N,M,next[200010],point[5010],v[200010],next2[200010],point2[5010],v2[200010];
double c[200010],c2[200010],dist[5010],duif[40000010],E,sum=0;
int cnt=0,cnt2=0,duiu[40000010];
bool vis[5010];
void insect(int x,int y,double z){cnt++;next[cnt]=point[x];point[x]=cnt;v[cnt]=y;c[cnt]=z;}
void insect2(int x,int y,double z){cnt2++;next2[cnt2]=point2[x];point2[x]=cnt2;v2[cnt2]=y;c2[cnt2]=z;}
void swapp(double &x,double &y){double z=x;x=y;y=z;}
void swapp2(int &x,int &y){int z=x;x=y;y=z;}
void SPFA()
{
int i,u; queue<int>q;
for (i=1;i<N;++i) dist[i]=1e150; memset(vis,0,sizeof(vis));
dist[N]=0; vis[N]=1; q.push(N);
while (!q.empty())
{
u=q.front(); q.pop();
for (i=point2[u];i!=0;i=next2[i])
if (dist[v2[i]]>dist[u]+c2[i])
{
dist[v2[i]]=dist[u]+c2[i];
if (vis[v2[i]]==0) {vis[v2[i]]=1;q.push(v2[i]);}
}
}
}
void weihu()
{
duiu[1]=duiu[duin];duif[1]=duif[duin];duin--;
int i=1;
while (i<duin)
{
if (((i*2+1>duin)||(duif[i]<duif[i*2+1]))&&((i*2>duin)||(duif[i]<duif[i*2])))
return;
if (i*2+1<=duin)
if (duif[i*2+1]<duif[i*2])
{
swapp(duif[i*2+1],duif[i]);
swapp2(duiu[i*2+1],duiu[i]); i=i*2+1;
}
else
{
swapp(duif[i*2],duif[i]);
swapp2(duiu[i*2],duiu[i]); i=i*2;
}
else
{
swapp(duif[i*2],duif[i]);
swapp2(duiu[i*2],duiu[i]); i=i*2;
}
}
}
void indui(int u,double f)
{
duin++;duiu[duin]=u;duif[duin]=f;
int i=duin;
while (i>1)
{
if (duif[i]>duif[i/2]) return;
else {swapp(duif[i],duif[i/2]);swapp2(duiu[i],duiu[i/2]); i=i/2;}
}
}
void astar()
{
int u,i,u2; double f,g,f2,g2; cnt=0;
duin=1; duiu[1]=1; duif[1]=dist[1];
while (duin>0)
{
u=duiu[1];f=duif[1];g=f-dist[u]; weihu();
if (u==N){sum+=f; if (sum<=E) {cnt++;continue;} else return;}
for (i=point[u];i!=0;i=next[i])
{
u2=v[i]; g2=g+c[i]; f2=g2+dist[u2];
indui(u2,f2);
}
}
}
int main()
{
scanf("%d %d %lf
",&N,&M,&E);
int i,x,y;double z;
for (i=1;i<=M;++i)
{
scanf("%d %d %lf
",&x,&y,&z);
insect(x,y,z); insect2(y,x,z);
}
SPFA();
astar();
printf("%d
",cnt);
return 0;
}
这样就行啦