제출 #1257414

#제출 시각아이디문제언어결과실행 시간메모리
1257414chautanphatConstruction Project 2 (JOI24_ho_t2)C++20
100 / 100
127 ms23340 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 1; vector<pair<int, int>> a[N]; vector<long long> dijkstra(int s) { vector<long long> d(N, 1e16); priority_queue<pair<long long, int>> q; d[s] = 0; q.push({0, s}); while (!q.empty()) { long long w; int u; tie(w, u) = q.top(); q.pop(); if (d[u] != -w) continue; for (auto [v, w] : a[u]) { if (d[u]+w < d[v]) { d[v] = d[u]+w; q.push({-d[v], v}); } } } return d; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, s, t, l; long long k; cin >> n >> m >> s >> t >> l >> k; while (m--) { int u, v, w; cin >> u >> v >> w; a[u].push_back({v, w}); a[v].push_back({u, w}); } vector<long long> ds = dijkstra(s), dt = dijkstra(t); if (ds[t] <= k) { cout << 1ll*n*(n-1)/2; return 0; } sort(ds.begin()+1, ds.end()); sort(dt.begin()+1, dt.end()); long long ans = 0; for (int i = 1, j = n; i <= n; i++) { while (j > 0 && ds[i]+dt[j]+l > k) j--; ans += j; } 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...