https://www.lydsy.com/JudgeOnline/problem.php?id=1975
我好像到现在了第k短路都不会写，mdzz。
先spfa求出最短路，然后扫点存各种前置路径已经决定的最短路，小根堆暴力即可。
有向图要存反向边，写完才发现的，临时添成两种了，丑也没办法
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define pa pair<double,int>
const int maxn=;
const double inf=1e17;
int n,m;double ene;
struct nod{
int y,next;double v;
}e[][maxn*];
int head[][maxn]={},tot[]={};
double dis[maxn]={};
bool vis[maxn]={};
queue<int>q;
priority_queue< pa , vector< pa > , greater< pa > >q1;
void init(int x,int y,double v,int op){
e[op][++tot[op]].v=v;e[op][tot[op]].y=y;e[op][tot[op]].next=head[op][x];head[op][x]=tot[op];
}
void spfa(){
for(int i=;i<=n;i++)dis[i]=inf;
dis[n]=;vis[n]=;q.push(n);
int x,y;double v;
while(!q.empty()){
x=q.front();q.pop();
for(int i=head[][x];i;i=e[][i].next){
y=e[][i].y;v=e[][i].v;
//cout<<x<<y<<v<<dis[y]<<endl;
if(dis[y]>dis[x]+v){
dis[y]=dis[x]+v;
if(!vis[y]){
vis[y]=;
q.push(y);
}
}
}vis[x]=;
}
}
int getit(){
q1.push(make_pair(dis[],));
int ans=;double vq,v;int x;
while(!q1.empty()){
x=q1.top().second; v=q1.top().first; q1.pop();
vq=v-dis[x];
if(x==n){
if(ene-v>=){ene-=v;ans++;}
else break;
}
for(int i=head[][x];i;i=e[][i].next){
q1.push(make_pair(vq+e[][i].v+dis[e[][i].y],e[][i].y));
}
}
return ans;
}
int main(){
scanf("%d%d%lf",&n,&m,&ene);
int x,y;double v;
for(int i=;i<=m;i++){scanf("%d%d%lf",&x,&y,&v);init(x,y,v,);init(y,x,v,);}
spfa();
printf("%d\n",getit());
return ;
}