Submission #1212265

#TimeUsernameProblemLanguageResultExecution timeMemory
1212265stefanneaguConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
3 ms5192 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int nmax = 2e5 + 1, inf = 1e17; 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(-5 * inf); for (int i = 1; i <= n; i++) { v.push_back(d2[i]); } sort(v.begin(), v.end()); int ans = 0; for (int i = 1; i <= n; i++) { int ind = upper_bound(v.begin(), v.end(), k - d1[i] - c) - v.begin() - 1; ans += ind; if (d1[i] + c + d2[i] <= k) { ans--; } } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...