```cpp
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5e3+5;
namespace IO_ReadWrite {
#define re register
#define gg (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
template <typename T>
inline void read(T &x){
x = 0; re T f=1; re char c = gg;
while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
x *= f;return;
}
inline void ReadChar(char &c){
c = gg;
while(!isalpha(c)) c = gg;
}
template <typename T>
inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x/10);
putchar('0' + x % 10);
}
template <typename T>
inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
int n,m,s=1,t,k,cnt[maxn];
double f[maxn],W;
bool vis[maxn];
int tot,head[maxn][2],ver[200005][2],nxt[200005][2];
double len[200005][2];
inline void add(int u,int v,double w){
ver[++tot][0]=v;nxt[tot][0]=head[u][0];len[tot][0]=w;head[u][0]=tot;
ver[tot][1]=u;nxt[tot][1]=head[v][1];len[tot][1]=w;head[v][1]=tot;
}
//vector<pair<int,double> > e[maxn],fe[maxn];
struct node{
double dis;
int now;
bool operator <(const node &x)const{
return dis<x.dis;
}
};
priority_queue<node> q;
inline void dijkstra(){
rep(i,1,n) f[i]=2e9+7;
memset(vis,0,sizeof(vis));
f[t]=0;
q.push((node){0.0,t});
while(!q.empty()){
int u=q.top().now;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u][1];i;i=nxt[i][1]){
int v=ver[i][1];
double w=len[i][1];
if(f[v]>f[u]+w){
f[v]=f[u]+w;
q.push((node){-f[v],v});
}
}
}
}
int ans=0;
inline void bfs(){
q.push((node){-f[s],s});
memset(cnt,0,sizeof(cnt));
while(!q.empty()){
int u=q.top().now;
double dist=-q.top().dis-f[u];
if(dist>W) return;
q.pop();
cnt[u]++;
if(u==t){
W-=dist;
ans++;
continue;
}
if(cnt[u]>k) continue;
for(int i=head[u][0];i;i=nxt[i][0]){
int v=ver[i][0];
double w=len[i][0];
q.push((node){-f[v]-dist-w,v});
}
}
}
int main(){
scanf("%d%d",&n,&m);scanf("%lf",&W);
rep(i,1,m){
int u,v;
double w;
scanf("%d%d",&u,&v);
scanf("%lf",&w);
add(u,v,w);
}
s=1,t=n;
dijkstra();
k=W/f[1];
bfs();
writeln(ans);
return 0;
}
```
by Mars_Dingdang @ 2021-04-05 10:48:01
A*早卡了
by iorit @ 2021-04-05 10:49:52