#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=2e5+10;
int n,m,s,t,l,k,ans;
int f[N],g[N],vis[N];
vector<pii>v[N];
void dijkstra(int id,int s,int dis[])
{
	memset(vis,0,sizeof(vis));
	priority_queue<pii,vector<pii>,greater<pii>>q;
	dis[s]=0,q.push({0,s});
	while(!q.empty())
	{
		auto [y,x]=q.top();
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(auto [i,j]:v[x])
		{
			if(dis[i]<=y+j)continue;
			dis[i]=y+j,q.push({dis[i],i});
		}
	}
}
signed main()
{
	cin>>n>>m;
	cin>>s>>t>>l>>k;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
	memset(f,127,sizeof(f));
	dijkstra(0,s,f);
	memset(g,127,sizeof(g));
	dijkstra(1,t,g);
	if(f[t]<=k)return cout<<n*(n-1)/2,0;
	sort(f+1,f+1+n);
	sort(g+1,g+1+n);
	for(int i=1;i<=n;i++)
	{
		if(f[i]>k-l)break;
		int id=upper_bound(g+1,g+1+n,k-f[i]-l)-g-1;
		ans+=id;
	}
	cout<<ans;
	return 0;
}

在不新建铁路线的图上跑最短路，定义此时 $x,y$ 间的最短路长为 $dis(x,y)$。

特判掉 $dis(S,T)\leq K$ 的情况（所有方案均合法），此时我们要求的就是满足 $dis(S,u)+L+dis(T,v)\leq K$ 的无序二元组 $(u,v)$ 数量。

令 $a_i=dis(T,i)$，将 $a$ 数组从小到大排序。枚举 $u$，则满足条件的 $v$ 数量有 $p$ 个，其中 $p$ 为最大的满足 $dis(S,u)\leq K-L-a_p$ 的数（不存在则为 $0$），直接 $\rm upper\_bound$ 即可。

答案为 $\sum p$，时间复杂度 $O(m\log m+n\log n)$。

关于上述解法你或许会有个小小的疑惑：若一个二元组 $(u,v)$ 同时满足 $dis(S,u)+L+dis(T,v)\leq K$ 和 $dis(S,v)+L+dis(T,u)\leq K$，这样算不会算重吗？

答案是这种情况不存在。证明比较简单，这里不再展开。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
const int N=2e5+10,M=N<<1;
struct ok{
    int x;ll y;
    bool operator <(const ok &A) const{return y>A.y;}
};
int n,m,S,T,L;
int first[N],to[M],nxt[M],lth[M],cnt;
bool vis[N];
ll K,ans,a[N],dis[N][2];
priority_queue<ok>q;
inline void inc(int x,int y,int l) {nxt[++cnt]=first[x],to[cnt]=y,first[x]=cnt,lth[cnt]=l;}
void Dij(int fi,bool p)
{
    for(int i=1;i<=n;i++)
        vis[i]=0,dis[i][p]=1e18;
    dis[fi][p]=0,q.push((ok){fi,0});
    while(!q.empty())
    {
        int x=q.top().x;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=first[x],v;i;i=nxt[i])
            if(dis[v=to[i]][p]>dis[x][p]+lth[i])
                dis[v][p]=dis[x][p]+lth[i],q.push((ok){v,dis[v][p]});
    }
}
int main()
{
    n=read(),m=read(),S=read(),T=read(),L=read(),K=read();
    int u,v,w;
    while(m--)
        u=read(),v=read(),w=read(),inc(u,v,w),inc(v,u,w);
    Dij(S,0),Dij(T,1);
    if(dis[T][0]<=K) return printf("%lld\n",1ll*n*(n-1)/2),0;
    for(int i=1;i<=n;i++) a[i]=dis[i][1];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        ans+=upper_bound(a+1,a+n+1,K-L-dis[i][0])-a-1;
    printf("%lld\n",ans);
    return 0;
}