Submission #1201994

#TimeUsernameProblemLanguageResultExecution timeMemory
1201994ZsofiaKeresztelyConstruction Project 2 (JOI24_ho_t2)C++20
100 / 100
140 ms24916 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pii pair<ll, ll> #define fi first #define se second vector<vector<pii> > g; vector<vector<ll> > d; void dijkstra(ll start, ll type){ priority_queue<pii> pq; pq.push({0, start}); while (!pq.empty()){ pii v = pq.top(); pq.pop(); //cout << "huhh" << v.se; if (d[type][v.se] >= 0) continue; d[type][v.se] = -v.fi; for (pii x : g[v.se]){ if (d[type][x.fi] < 0){ //cout << "huhi" << x.fi; pq.push({v.fi-x.se, x.fi}); } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll n, m, s, t, l, k; cin >> n >> m >> s >> t >> l >> k; g.resize(n+1); d.assign(2, vector<ll>(n+1, -1)); while (m--){ ll a, b, c; cin >> a >> b >> c; g[a].push_back({b, c}); g[b].push_back({a, c}); } dijkstra(s, 0); dijkstra(t, 1); /*for (ll i=0; i<=n; i++){ cout << i << " " << d[0][i] << " " << d[1][i] << "\n"; }*/ if (d[0][t] >= 0 && d[0][t] <= k){ cout << n * (n-1) / 2; return 0; } sort(d[0].begin(), d[0].end()); sort(d[1].begin(), d[1].end()); k -= l; ll pt = n, op = 0, nav = 0; while (nav < n && d[1][nav+1]){ nav++; } for (ll i=1; i<=n; i++){ if (d[0][i] == -1) continue; while (pt > nav && d[0][i] + d[1][pt] > k){ pt--; } op += pt - nav; } cout << op; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...