#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
void testcase(){
int N, M, S, T, L; long long K;
cin >> N >> M >> S >> T >> L >> K;
--S, --T;
vector<vector<pair<int, int>>> adj(N);
while(M--){
int u, v, w;
cin >> u >> v >> w;
--u, --v;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
auto dijkstra = [&](int s){
vector<long long> d(N, inf);
d[s] = 0;
using node = pair<long long, int>;
priority_queue<node, vector<node>, greater<node>> pq;
pq.push({d[s], s});
while(!pq.empty()){
long long cur; int u;
tie(cur, u) = pq.top(); pq.pop();
if(Cur != d[u]) continue;
for(auto [v, w] : adj[u]){
if(d[v] > d[u] + w){
d[v] = d[u] + w;
pq.push({d[v], v});
}
}
}
return d;
};
vector<long long> dS = dijkstra(S), dT = dijkstra(T);
if(dS[T] <= K){
cout << 1LL * N * (N - 1) / 2;
return;
}
vector<long long> vS, vT;
for(int i = 0; i < N; ++i){
vS.emplace_back(dS[i]);
vT.emplace_back(dT[i]);
}
sort(vS.begin(), vS.end());
sort(vT.rbegin(), vT.rend());
long long cnt = 0;
int v = 0;
for(auto val : vT){
while(v < (int)vS.size() && vS[v] <= K - L - val) ++v;
cnt += v;
}
cout << cnt << '\n';
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
// cin >> T;
while(T--) testcase();
return 0;
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:32:16: error: 'Cur' was not declared in this scope; did you mean 'cur'?
32 | if(Cur != d[u]) continue;
| ^~~
| cur
Main.cpp:33:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
33 | for(auto [v, w] : adj[u]){
| ^
