#include <bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define fi first
#define se second
typedef pair<int,int> pii;
#define pb push_back
bool svis[200005];
int sdis[200005];
bool tvis[200005];
int tdis[200005];
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m;cin>>n>>m;
int s,t,l,k;cin>>s>>t>>l>>k;
vector<pair<int,int>> adj[n+1];
for(int i=0;i<m;i++){
int x,y,w;cin>>x>>y>>w;
adj[x].pb({y,w});
adj[y].pb({x,w});
}
for(int i=0;i<=n;i++){
tdis[i]=LLONG_MAX;
sdis[i]=LLONG_MAX;
}
priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.push({0,s});
while(!pq.empty()){
int cd=pq.top().fi;
int cn=pq.top().se;
pq.pop();
if(svis[cn])continue;
svis[cn]=1;
sdis[cn]=cd;
for(pii p:adj[cn]){
if(svis[p.fi])continue;
pq.push({p.se+cd,p.fi});
}
}
pq.push({0,t});
while(!pq.empty()){
int cd=pq.top().fi;
int cn=pq.top().se;
pq.pop();
if(tvis[cn])continue;
tvis[cn]=1;
tdis[cn]=cd;
for(pii p:adj[cn]){
if(tvis[p.fi])continue;
pq.push({p.se+cd,p.fi});
}
}
if(tdis[s]<=k){
cout<<(n-1)*n/2<<'\n';
return 0;
}
vector<int> ss;
for(int i=1;i<=n;i++){
//debug(tdis[i])
ss.pb(tdis[i]);
}
sort(ss.begin(),ss.end());
//for(auto i:ss)debug(i)
//for(int i=0;i<n;i++)debug(tdis[i])
int ans=0;
for(int i=1;i<=n;i++){
int temp=(upper_bound(ss.begin(),ss.end(),(k-l-sdis[i]))-ss.begin());
if(sdis[i]==LLONG_MAX)continue;
//debug(sdis[i])
//debug(temp)
ans+=temp;
}
cout<<ans<<'\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |