bzoj1975 [Sdoi2010]魔法猪学院
k短路裸题
手写堆要开2e6...
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<queue>
#define Fname "2483"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define db double
typedef long long ll;
il int gi(){
rg int x=0;rg bool flg=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return flg?-x:x;
}
il db gf(){static db ls;scanf("%lf",&ls);return ls;}
const int maxn=5010,maxm=200010<<1;
int fir[maxn],dis[maxm],nxt[maxm],id;db w[maxm];
il vd add(int a,int b,db c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}
int n,m;db e;
db g[maxn];
struct node{
db d;short s;
bool operator <(const node&other)const{return g[s]+d<g[other.s]+other.d;}
bool operator >(const node&other)const{return g[s]+d>g[other.s]+other.d;}
}p[2000100];
int siz;
#define ls (x<<1)
#define rs (x<<1|1)
#define fa (x>>1)
il vd pushup(int x){
while(x^1){
if(p[x]>p[fa])return;
swap(p[x],p[fa]),x=fa;
}
}
il vd pushdown(int x){
while(ls<=siz){
if(ls==siz){
if(p[x]>p[ls])swap(p[x],p[ls]);
break;
}
if(p[ls]<p[x])
if(p[rs]<p[ls])swap(p[x],p[rs]),x=rs;
else swap(p[x],p[ls]),x=ls;
else if(p[rs]<p[x])swap(p[x],p[rs]),x=rs;
else break;
}
}
il vd push(const int&x,db y){if(y<=e)p[++siz]=(node){y,x},pushup(siz);}
il vd pop(node&a){a=p[1],p[1]=p[siz--],pushdown(1);}
#undef ls
#undef rs
#undef fa
il vd spfa(){
rep(i,1,n-1)g[i]=1e14;
int que[maxn],hd=0,tl=0;bool inque[maxn]={0};
que[tl++]=n,inque[n]=1;
while(hd^tl){
static int x;x=que[hd];
erep(i,x)if((i&1)==0)
if(g[dis[i]]>w[i]+g[x]){
g[dis[i]]=w[i]+g[x];
if(!inque[dis[i]])inque[dis[i]]=1,que[tl++]=dis[i],tl%=maxn;
}
++hd,hd%=maxn,inque[x]=0;
}
}
priority_queue<db>que;
il vd Astar(){
push(1,0.0f);
db sum=0;
while(siz){
static node x;pop(x);
if(sum+x.d>e)continue;
if(x.s==n){
que.push(x.d),sum+=x.d;
while(sum>e)sum-=que.top(),que.pop();
continue;
}
else erep(i,x.s)if(i&1)push(dis[i],x.d+w[i]);
}printf("%d
",que.size());
}
int main(){
#ifdef xzz
freopen(Fname".in","r",stdin);
freopen(Fname".out","w",stdout);
#endif
n=gi(),m=gi(),e=gf();
int x,y;db z;
while(m--)x=gi(),y=gi(),z=gf(),add(x,y,z),add(y,x,z);
spfa(),Astar();
return 0;
}