#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb(a) push_back(a)
#define pp pop_back
#define mp(a, b) make_pair(a, b)
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m, s, t, l, k;
cin >> n >> m >> s >> t >> l >> k;
vector <pair <int, int> > adj[n+1];
int a, b, c;
for (int i=0; i<m; i++) {
cin >> a >> b >> c;
adj[a].pb(mp(c, b));
adj[b].pb(mp(c, a));
}
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
int x[n+1], y[n+1];
for (int i=1; i<=n; i++) {x[i]=LLONG_MAX; y[i]=LLONG_MAX;}
x[s]=0;
pq.push(mp(0, s));
while (!pq.empty()) {
pair <int, int> p=pq.top();
pq.pop();
if (p.first!=x[p.second]) continue;
for (auto i:adj[p.second]) {
if (x[i.second]>x[p.second]+i.first) {
x[i.second]=x[p.second]+i.first;
pq.push(mp(x[i.second], i.second));
}
}
}
if (x[t]<=k) {cout << n*(n-1)/2 << "\n"; return 0;}
sort(x+1, x+n+1, greater<int>());
int tot=0, idx=1;
y[t]=0;
pq.push(mp(0, t));
while (!pq.empty()) {
pair <int, int> p=pq.top();
while (idx<=n && x[idx]>k-l-pq.top().first) idx++;
tot+=n+1-idx;
pq.pop();
if (p.first!=y[p.second]) continue;
for (auto i:adj[p.second]) {
if (y[i.second]>y[p.second]+i.first) {
y[i.second]=y[p.second]+i.first;
pq.push(mp(y[i.second], i.second));
}
}
}
cout << tot << "\n";
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... |