#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
vector<vector<pii> > g;
vector<vector<ll> > d;
void dijkstra(ll start, ll type){
priority_queue<pii> pq;
pq.push({0, start});
while (!pq.empty()){
pii v = pq.top();
pq.pop();
//cout << "huhh" << v.se;
if (d[type][v.se] >= 0) continue;
d[type][v.se] = -v.fi;
for (pii x : g[v.se]){
if (d[type][x.fi] < 0){
//cout << "huhi" << x.fi;
pq.push({v.fi-x.se, x.fi});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, m, s, t, l, k;
cin >> n >> m >> s >> t >> l >> k;
g.resize(n+1);
d.assign(2, vector<ll>(n+1, -1));
while (m--){
ll a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
dijkstra(s, 0);
dijkstra(t, 1);
/*for (ll i=0; i<=n; i++){
cout << i << " " << d[0][i] << " " << d[1][i] << "\n";
}*/
if (d[0][t] >= 0 && d[0][t] <= k){
cout << n * (n-1) / 2;
return 0;
}
sort(d[0].begin(), d[0].end());
sort(d[1].begin(), d[1].end());
k -= l;
ll pt = n, op = 0, nav = 0;
while (nav < n && d[1][nav+1]){
nav++;
}
for (ll i=1; i<=n; i++){
if (d[0][i] == -1) continue;
while (pt > nav && d[0][i] + d[1][pt] > k){
pt--;
}
op += pt - nav;
}
cout << op;
}
# | 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... |