说实话，看到这道题的洛谷评级我傻了（传说中的最高难度）
然后看完题目才确定这真的是一道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=5005; 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=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int main() { read(n); read(m); scanf("%lf",&tot); for (i=1;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=1;i<=n;++i) dis[i]=1e9; dis[n]=0; small.push((data){n,0}); while (!small.empty()) { int now=small.top().num; small.pop(); if (vis[now]) continue; vis[now]=1; for (i=0;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){1,0,dis[1]}); 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 0; } else ans++,sum+=temp; } for (i=0;i<a[now].size();++i) tree.push((Astar){a[now][i],temp+l[now][i],dis[a[now][i]]}); } return 0; }