/*
Mayoeba Yabureru
*/
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
long long dis[2][200002];
vector<vector<int>> gr[200002];
void solve() {
long long n, m, s, t, l, k;
cin >> n >> m >> s >> t >> l >> k;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
gr[a].push_back({b, c});
gr[b].push_back({a, c});
}
long long kl = k - l;
// a + b <= kl
for (int i = 0; i <= 1; i ++) {
for (int j = 1; j <= n; j ++) dis[i][j] = 1e17;
}
dis[0][s] = 0;
dis[1][t] = 0;
priority_queue<vector<long long>> pq;
pq.push({0, 0, s});
pq.push({0, 1, t});
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
if (-p[0] > dis[p[1]][p[2]]) continue;
int c = p[1], v = p[2];
for (auto u : gr[v]) {
if (dis[c][u[0]] > dis[c][v] + u[1]) {
dis[c][u[0]] = dis[c][v] + u[1];
pq.push({-dis[c][u[0]], c, u[0]});
}
}
}
if (dis[0][t] <= k) {
cout << (n * (n - 1)) / 2;
return;
}
vector vs(0, 0ll), vt(0, 0ll);
for (int i = 1; i <= n; i++) {
vs.push_back(dis[0][i]);
vt.push_back(dis[1][i]);
}
sort(vs.rbegin(), vs.rend());
sort(vt.begin(), vt.end());
long long ans = 0;
int j = 0;
for (int i = 0; i < vs.size(); i++) {
while (j < vt.size() && vs[i] + vt[j] <= kl) {
j++;
}
ans += j;
}
for (int i = 1; i <= n; i ++) {
if (dis[0][i] + dis[1][i] + l <= k) ans --;
}
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
for (int I = 1; I <= T; I++) {
solve();
}
}
# | 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... |