重新发波代码
```cpp
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const double eps=1e-7;
int h[5001],ne[400001],to[400001],en=0;
double w[400001],f[5001],e;
int inq[5001],n,m,ans=0;
struct node{
int now;
double step;
double g;
bool operator < (node x) const{
return (g==x.g)?step>x.step:g>x.g;
}
};
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int a,int b,double c)
{ne[en]=h[a];to[en]=b;w[en]=c;h[a]=en++;}
inline void SPFA1()
{
memset(f,127,sizeof f);
f[n]=0;inq[n]=1;
queue<int>q;
q.push(n);
while (!q.empty())
{
int x=q.front();q.pop();inq[x]=0;
for (register int i=h[x];i>=0;i=ne[i])
if (i&1){
if (f[to[i]]>f[x]+w[i])
{
f[to[i]]=f[x]+w[i];
if (!inq[to[i]])
{
inq[to[i]]=1;
q.push(to[i]);
}
}
}
}
}
inline void Astar()
{
priority_queue<node>q;
node S;
S.now=1;
S.step=0;
S.g=S.step+f[S.now];
q.push(S);
while (!q.empty()&&(e+eps>0))
{
node x=q.top();q.pop();
if (x.now==n)
{
if (e-x.step+eps>0) ans++,e-=x.step;
else e=-100;
}
if (x.g>e) break;
for (register int i=h[x.now];i>=0;i=ne[i])
if (!(i&1)){
node next;
next.now=to[i];
next.step=x.step+w[i];
next.g=next.step+f[next.now];
if (next.g>e) continue;
q.push(next);
}
}
}
int main()
{
memset(h,-1,sizeof h);
n=read();m=read();
scanf("%lf",&e);
for (register int i=1;i<=m;++i)
{
int a,b;
double c;
a=read();b=read();
scanf("%lf",&c);
add(a,b,c);
add(b,a,c);
}
SPFA1();
Astar();
printf("%d\n",ans);
}
```
by SNiFe @ 2018-03-15 07:29:13
好像有坑......
# ~~特判一下就过了~~
by SofanHe @ 2018-03-20 10:41:36
Astar是不能过k短路的
已经被hack掉了
推荐看[这个](https://blog.csdn.net/wyfcyx_forever/article/details/45875055)
by Kelin @ 2018-04-04 17:19:42