你谷数据够强了，以前的A*应该差不多死掉了。
所以，小伙伴们快来一起把YL顶上去把！戳这里！
需要掌握的内容：
Dijkstra构建最短路径树。
可持久化堆（使用左偏树，因其有二叉树结构且能动态合并。构建方法类似可持久化线段树）。
#include<bits/stdc++.h>
#define RG register
#define R RG int
using namespace std;
const int N=5009,M=4e5+9;
int p,he[N],re[N],ne[M],to[M],f[N],rt[N];
double w[M],d[N];bool vis[N];
struct Heap{
double w;
int lc,rc,dep,end;
}t[M];//不要问我为什么过了
struct Node{
double w;int x;
inline bool operator<(RG Node a)const{
return w>a.w;
}
};
priority_queue<Node>q;
int merge(R x,R y,R op){//左偏树合并，op控制是否复制版本
if(!(x&&y))return x+y;
if(t[x].w>t[y].w)swap(x,y);
if(op)t[++p]=t[x],x=p;
t[x].rc=merge(t[x].rc,y,op);
if(t[t[x].lc].dep<t[t[x].rc].dep)swap(t[x].lc,t[x].rc);
t[x].dep=t[t[x].rc].dep+1;
return x;
}
int main(){
ios::sync_with_stdio(0);
R n,m,i,x,y,ans=0;
RG double E,now;
cin>>n>>m>>E;
for(i=1;i<=m;++i){
cin>>x>>y>>w[i];
ne[ i ]=he[x];to[he[x]= i ]=y;
ne[i+m]=re[y];to[re[y]=i+m]=x;
}
for(x=1;x<n;++x)d[x]=1e18;
q.push((Node){0,n});//Dijkstra开始
while(!q.empty()){
x=q.top().x;q.pop();
if(vis[x])continue;
vis[x]=1;
for(i=re[x];i;i=ne[i])
if(d[y=to[i]]>d[x]+w[i-m])
q.push((Node){d[y]=d[x]+w[i-m],y});
}
for(x=1;x<=n;++x){
if(d[x]==1e18)continue;
for(i=he[x];i;i=ne[i]){
if(d[x]==d[y=to[i]]+w[i]&&!f[x])f[x]=y;//构建最短路树
else if(d[y]!=1e18){
t[++p]=(Heap){d[y]+w[i]-d[x],0,0,1,y};
rt[x]=merge(rt[x],p,0);
}
}
q.push((Node){d[x],x});
}
while(!q.empty()){
x=q.top().x;q.pop();
if(f[x])rt[x]=merge(rt[x],rt[f[x]],1);//可持久化
}
if(E>=d[1])E-=d[1],++ans;
if(rt[1])q.push((Node){t[rt[1]].w,rt[1]});
while(!q.empty()){
now=q.top().w;x=q.top().x;q.pop();
if(E<now+d[1])break;
E-=now+d[1];++ans;
if((y=t[x].lc))q.push((Node){now-t[x].w+t[y].w,y});
if((y=t[x].rc))q.push((Node){now-t[x].w+t[y].w,y});
if((y=rt[t[x].end]))q.push((Node){now+t[y].w,y});
}
printf("%d
",ans);
return 0;
}