#include <bits/stdc++.h>
#define int long long
using namespace std;
const int nmax = 2e5 + 1, inf = 1e18;
vector<pair<int, int>> adj[nmax];
int d1[nmax];
int d2[nmax];
int n;
void dij1(int root) {
for (int i = 1; i <= n; i++) {
d1[i] = inf;
}
priority_queue<pair<int, int>> pq;
pq.push({0, root});
d1[root] = 0;
while (!pq.empty()) {
auto [sum, i] = pq.top();
pq.pop();
if (sum > d1[i]) {
continue;
}
for (auto [it, c] : adj[i]) {
if (d1[it] > sum + c) {
d1[it] = sum + c;
pq.push({d1[it], it});
}
}
}
}
void dij2(int root) {
for (int i = 1; i <= n; i++) {
d2[i] = inf;
}
priority_queue<pair<int, int>> pq;
pq.push({0, root});
d2[root] = 0;
while (!pq.empty()) {
auto [sum, i] = pq.top();
pq.pop();
if (sum > d2[i]) {
continue;
}
for (auto [it, c] : adj[i]) {
if (d2[it] > sum + c) {
d2[it] = sum + c;
pq.push({d2[it], it});
}
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int m, s, t, c, k;
cin >> n >> m >> s >> t >> c >> k;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
dij1(s);
dij2(t);
vector<int> v;
v.push_back(-inf);
for (int i = 1; i <= n; i++) {
v.push_back(d2[i]);
}
cout << '\n';
sort(v.begin(), v.end());
int ans = 0;
for (int i = 1; i <= n; i++) {
int ind = lower_bound(v.begin(), v.end(), k - d1[i] - c) - v.begin();
if (v[ind] + d1[i] + c > k) {
ind--;
}
ans += ind;
if (d1[i] + c + d2[i] == k) {
ans--;
}
}
cout << ans;
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... |