Submission #976523

#TimeUsernameProblemLanguageResultExecution timeMemory
976523MarcusCyberland (APIO23_cyberland)C++17
68 / 100
278 ms11048 KiB
#include <bits/stdc++.h> using namespace std; double const INF = 1e105; int const N = 1e5; vector<vector<pair<int, int>>> adj(N); vector<double> dist(N); vector<double> dist2(N); vector<bool> processed(N); priority_queue<pair<double, int>> q; double answer = INF; void dijkstra(int number, int target) { for (int z=0; z<number; z++) {processed[z] = false;} //dist[0] = 0; for (int z = 0; z<number; z++) if (dist[z] < INF) q.push({-dist[z], z}); while (!q.empty()) { int a = q.top().second; q.pop(); if (processed[a] || a == target) continue; processed[a] = true; for (auto u : adj[a]) { int b = u.first, w = u.second; if (dist[a]+w < dist[b]) { dist[b] = dist[a]+w; q.push({-dist[b],b}); } } } answer = min(answer, dist[target]); } double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { answer = INF; for(int i = 0; i < n; i++) adj[i].clear(); for (int i=0; i<m; i++) { int v = x[i]; int u = y[i]; int w = c[i]; adj[v].push_back({u, w}); adj[u].push_back({v, w}); } for (int i=0; i<n; i++) {dist[i] = INF;} dist[0] = 0; dijkstra(n, h); if (dist[h] >= INF) {return -1;} for (int i=0; i<n; i++) {if (dist[i] != INF) dist[i] = ((arr[i] && i) ? INF : 0);} k = min(k, 67); for (int i=1; i<=k; i++) { dijkstra(n, h); for (int j=0; j<n; j++) {dist2[j] = INF;} for (int j=0; j<n; j++) { if (arr[j] == 2) { for (auto p: adj[j]) { int u = p.first; int w = p.second; dist2[u] = min(dist2[u], dist[j]/2+w); } } } for (int j=0; j<n; j++) {dist[j] = dist2[j];} } return answer; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...