Submission #1274886

#TimeUsernameProblemLanguageResultExecution timeMemory
1274886AbdullahIshfaqConstruction Project 2 (JOI24_ho_t2)C++20
8 / 100
116 ms23672 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define MOD 998244353 const int N = 200'005; vector<pair<ll, ll>> g[N]; void solve() { ll n, m, s, t, l, k, u, v, c, ans = 0; cin >> n >> m; cin >> s >> t >> l >> k; ll dists[n + 1], distt[n + 1]; for (int i = 0; i <= n; i++) { dists[i] = distt[i] = 1e18; } for (int i = 0; i < m; i++) { cin >> u >> v >> c; g[u].push_back({v, c}); g[v].push_back({u, c}); } priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; dists[s] = 0; pq.push({0, s}); while (!pq.empty()) { auto [w, u] = pq.top(); pq.pop(); for (auto [i, j] : g[u]) { if (dists[u] + j < dists[i] and dists[i] == 1e18) { dists[i] = dists[u] + j; pq.push({dists[i], i}); } } } distt[t] = 0; pq.push({0, t}); while (!pq.empty()) { auto [w, u] = pq.top(); pq.pop(); for (auto [i, j] : g[u]) { if (distt[u] + j < distt[i] and distt[i] == 1e18) { distt[i] = distt[u] + j; pq.push({distt[i], i}); } } } for (int i = 1; i <= n; i++) { if (dists[i] + distt[i] <= k) { cout << (n * (n - 1)) / 2 << '\n'; return; } } sort(distt, distt + n + 1); k -= l; for (int i = 1; i <= n; i++) { ans += upper_bound(distt, distt + n + 1, k - dists[i]) - distt; } cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tests = 1; // cin >> tests; for (int i = 1; i <= tests; i++) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...