#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define int long long
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, s, t, l, k;
cin >> n >> m >> s >> t >> l >> k;
vector<vector<pair<int, int> > > g(n+1);
for(int i = 0, u, v, w; i < m; ++i){
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
const int no_path = 1e18;
auto djikstra = [&](int from){
vector<int> dist(n+1, no_path);
priority_queue<pair<int, int>> q;
dist[from] = 0;
q.emplace(0, from);
while(!q.empty()){
auto [W, v] = q.top();
q.pop();
if(W != dist[v]) continue;
for(auto [u, w]:g[v])
if(dist[u] > W + w){
dist[u] = W + w;
q.emplace(dist[u], u);
}
}
return dist;
};
auto from_s = djikstra(s);
if(from_s[t] <= k){
cout << n * (n - 1) / 2;
return 0;
}
if(l > k){
cout << 0;
return 0;
}
auto from_t = djikstra(t);
sort(from_s.begin(), from_s.end());
sort(from_t.begin(), from_t.end());
int res = 0;
k -= l;
for(int i = 0, j = n - 1; i < n; ++ i){
while(j >= 0 && from_s[i] + from_t[j] > k) -- j;
res += j + 1;
}
cout << res;
return 0;
}
# | 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... |