제출 #1212479

#제출 시각아이디문제언어결과실행 시간메모리
1212479mdn2002Construction Project 2 (JOI24_ho_t2)C++20
100 / 100
309 ms53464 KiB
/* Mayoeba Yabureru */ #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> using namespace std; long long dis[2][200002]; vector<vector<int>> gr[200002]; void solve() { long long n, m, s, t, l, k; cin >> n >> m >> s >> t >> l >> k; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; gr[a].push_back({b, c}); gr[b].push_back({a, c}); } long long kl = k - l; // a + b <= kl for (int i = 0; i <= 1; i ++) { for (int j = 1; j <= n; j ++) dis[i][j] = 1e17; } dis[0][s] = 0; dis[1][t] = 0; priority_queue<vector<long long>> pq; pq.push({0, 0, s}); pq.push({0, 1, t}); while (!pq.empty()) { auto p = pq.top(); pq.pop(); if (-p[0] > dis[p[1]][p[2]]) continue; int c = p[1], v = p[2]; for (auto u : gr[v]) { if (dis[c][u[0]] > dis[c][v] + u[1]) { dis[c][u[0]] = dis[c][v] + u[1]; pq.push({-dis[c][u[0]], c, u[0]}); } } } if (dis[0][t] <= k) { cout << (n * (n - 1)) / 2; return; } vector vs(0, 0ll), vt(0, 0ll); for (int i = 1; i <= n; i++) { vs.push_back(dis[0][i]); vt.push_back(dis[1][i]); } sort(vs.rbegin(), vs.rend()); sort(vt.begin(), vt.end()); long long ans = 0; int j = 0; for (int i = 0; i < vs.size(); i++) { while (j < vt.size() && vs[i] + vt[j] <= kl) { j++; } ans += j; } for (int i = 1; i <= n; i ++) { if (dis[0][i] + dis[1][i] + l <= k) ans --; } cout << ans << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int T = 1; for (int I = 1; I <= T; 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...