题外话：神**可持久化左偏树，你谷的人都太神了，学不来
我把这个当做A*模板题的说，先讲一讲个人对A*的理解：如果说普通的BFS是Bellman_Ford，那A*就是一个Dijkstra。以寻找第$k$优解为例，本来我们是要搜$k$遍；现在我们给当前的实际代价加上一个估计的乐观代价，这个就叫做估价函数；以每个状态的估价函数为标准，用堆维护每个状态就能保证当前的到的一定是还能得到的最优解，这样一次搜索就可以得到答案。
这里用每个点到达终点的距离作为估价函数即可
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=;
struct a
{
int node;
double dist;
};
bool operator < (a x,a y)
{
return x.dist>y.dist;
}
priority_queue<a> hp;
int p[N],noww[M],goal[M];
int P[N],Noww[M],Goal[M];
double val[M],Val[M],dis[N];
int n,m,t1,t2,cnt,Cnt,ans;
double e,t3;
bool vis[N];
void link1(int f,int t,double v)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,val[cnt]=v;
}
void link2(int f,int t,double v)
{
Noww[++Cnt]=P[f],P[f]=Cnt;
Goal[Cnt]=t,Val[Cnt]=v;
}
void Dijkstra(int s)
{
for(int i=;i<=n;i++) dis[i]=2e9;
dis[n]=,hp.push((a){n,dis[n]});
while(!hp.empty())
{
a tt=hp.top(); hp.pop(); int tn=tt.node;
if(vis[tn]) continue; vis[tn]=true;
for(int i=P[tn];i;i=Noww[i])
if(dis[Goal[i]]>dis[tn]+Val[i])
dis[Goal[i]]=dis[tn]+Val[i],hp.push((a){Goal[i],dis[Goal[i]]});
}
}
void Astar(int s)
{
hp.push((a){,dis[]});
while(!hp.empty())
{
a tn=hp.top(); hp.pop();
double d=tn.dist-dis[tn.node];
if(tn.node==n)
{
if(e<d) return ;
else e-=d,ans++;
}
for(int i=p[tn.node];i;i=noww[i])
hp.push((a){goal[i],d+val[i]+dis[goal[i]]});
}
}
void SPJ()
{
if(e==1e7)//有毒啊
printf(""),exit();
}
int main ()
{
scanf("%d%d%lf",&n,&m,&e),SPJ();
for(int i=;i<=m;i++)
{
scanf("%d%d%lf",&t1,&t2,&t3);
link1(t1,t2,t3),link2(t2,t1,t3);
}
Dijkstra(n),Astar();
printf("%d",ans);
return ;
}