Submission #769946

#TimeUsernameProblemLanguageResultExecution timeMemory
769946gromperenCyberland (APIO23_cyberland)C++17
15 / 100
27 ms5716 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; #define ll long long const double INF = 1e18; double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { vector<ll> dist(N, INF); vector<vector<pair<int,int>>> adj(N); for (int i = 0; i < M; ++i) { adj[x[i]].push_back({y[i], c[i]}); adj[y[i]].push_back({x[i], c[i]}); } priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq; arr[0] = 0; pq.push({0,0}); //for (int i = 0; i < N; ++i) { //if (arr[i] == 0) pq.push({0, i}); //} while(!pq.empty()) { int cur = pq.top().second; ll d = pq.top().first; pq.pop(); if (dist[cur] < d) continue; dist[cur] = d; //if (arr[cur] == 0) return d; for (auto [nxt, cost] : adj[cur]) { if (arr[nxt] == 0 && dist[nxt] > 0) { dist[nxt] = 0; pq.push({0, nxt}); } if (dist[nxt] > d + cost) { dist[nxt] = d + cost; pq.push({dist[nxt], nxt}); } } } if (dist[H] == INF) return -1; return (double)dist[H]; }
#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...