说实话，看到这道题的洛谷评级我傻了（传说中的最高难度）
然后看完题目才确定这真的是一道k短路的裸题。
也就敲了个A*吧，15分钟竟然没有调试一遍过。
欧洲玄学。
看题目，主要是找几条从1走到n的路加起来小于等于给定的E即可。
所以就是一道k短路。
A*和DJ很像，就是把堆的比较操作从当前路径长度+该点到n点的长度。
后面的那个就是估价函数了，打SPFA或DJ都可以。
然后STL堆搞一波就可以了。
CODE
// luogu-judger-enable-o2
#include<cstdio>
#include<queue>
using namespace std;
typedef double DB;
const int N=;
struct data
{
int num;
DB s;
bool operator <(const data &a) const
{
return a.s<s;
}
};
struct Astar
{
int num;
DB s,rs;
bool operator <(const Astar &a) const
{
return a.s+a.rs<s+rs;
}
};
priority_queue <data> small;
priority_queue <Astar> tree;
vector <int> a[N],b[N];
vector <DB> l[N],rl[N];
int n,m,i,x,y,ans;
DB z,tot,dis[N],sum;
bool vis[N];
inline void read(int &x)
{
x=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
int main()
{
read(n); read(m); scanf("%lf",&tot);
for (i=;i<=m;++i)
{
read(x); read(y); scanf("%lf",&z);
a[x].push_back(y); l[x].push_back(z);
b[y].push_back(x); rl[y].push_back(z);
}
for (i=;i<=n;++i)
dis[i]=1e9;
dis[n]=;
small.push((data){n,});
while (!small.empty())
{
int now=small.top().num; small.pop();
if (vis[now]) continue;
vis[now]=;
for (i=;i<b[now].size();++i)
{
int k=b[now][i];
if (dis[k]>dis[now]+rl[now][i])
{
dis[k]=dis[now]+rl[now][i];
small.push((data){k,dis[k]});
}
}
}
tree.push((Astar){,,dis[]});
while (!tree.empty())
{
int now=tree.top().num; DB temp=tree.top().s; tree.pop();
if (now==n) { if (sum+temp>tot) { printf("%d",ans); return ; } else ans++,sum+=temp; }
for (i=;i<a[now].size();++i)
tree.push((Astar){a[now][i],temp+l[now][i],dis[a[now][i]]});
}
return ;
}