#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(x) (x).begin(),(x).end()
const ll INF = 1e18;
int main(){
cin.tie( nullptr );
ios::sync_with_stdio( false );
cout << setprecision( 12 ) << fixed;
ll n, m;
cin >> n >> m;
ll s, t, l, k;
cin >> s >> t >> l >> k;
--s;
--t;
vector<vector<pair<ll, ll>>> g(n);
for(int i = 0; i < m; ++i){
ll a, b, c;
cin >> a >> b >> c;
--a;
--b;
g[a].pb({b, c});
g[b].pb({a, c});
}
vector<ll> dists(n, INF);
dists[s] = 0;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
q.push({0, s});
while(!(q.empty())){
ll x = q.top().second;
ll d = q.top().first;
q.pop();
if(dists[x] != d) continue;
for(auto c: g[x]){
if(dists[c.first] > d + c.second){
dists[c.first] = d + c.second;
q.push({d + c.second, c.first});
}
}
}
if(dists[t] <= k){
cout << n * (n - 1) / 2 << endl;
return 0;
}
vector<ll> distt(n, INF);
distt[t] = 0;
q.push({0, t});
while(!(q.empty())){
ll x = q.top().second;
ll d = q.top().first;
q.pop();
if(distt[x] != d) continue;
for(auto c: g[x]){
if(distt[c.first] > d + c.second){
distt[c.first] = d + c.second;
q.push({d + c.second, c.first});
}
}
}
sort(all(distt));
ll ans = 0;
for(int i = 0; i < n; ++i){
ans += upper_bound(all(distt), k - dists[i] - l) - distt.begin();
}
cout << ans << endl;
}
# | 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... |