Submission #865336

#TimeUsernameProblemLanguageResultExecution timeMemory
865336jk410Cyberland (APIO23_cyberland)C++17
100 / 100
362 ms20280 KiB
#include "cyberland.h" #include <vector> #include <queue> #include <functional> using namespace std; struct edge{ int v; double cost; bool operator<(const edge &tmp)const{ return cost>tmp.cost; } }; const int MAXK=100; const double INF=1e15; vector<edge> Adj[100000]; bool Ikeru[100000]; double Dist[100000]; priority_queue<edge> PQ; double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){ for (int i=0; i<N; i++) Adj[i].clear(); fill(Ikeru,Ikeru+N,false); fill(Dist,Dist+N,INF); while (!PQ.empty()) PQ.pop(); for (int i=0; i<M; i++){ Adj[x[i]].push_back({y[i],(double)c[i]}); Adj[y[i]].push_back({x[i],(double)c[i]}); } function<void(int)> dfs=[&](int v){ Ikeru[v]=true; if (v==H) return; for (edge i:Adj[v]){ if (!Ikeru[i.v]) dfs(i.v); } }; dfs(0); if (!Ikeru[H]) return -1; K=min(K,MAXK)+1; for (int i=0; i<N; i++){ if (Ikeru[i]&&!arr[i]){ Dist[i]=0; PQ.push({i,0}); } } Dist[0]=0; PQ.push({0,0}); while (K--){ while (!PQ.empty()){ edge cur=PQ.top(); PQ.pop(); if (Dist[cur.v]<cur.cost||cur.v==H) continue; for (edge i:Adj[cur.v]){ if (Dist[i.v]>cur.cost+i.cost){ Dist[i.v]=cur.cost+i.cost; PQ.push({i.v,Dist[i.v]}); } } } for (int i=0; i<N; i++){ if (Ikeru[i]&&arr[i]==2){ PQ.push({i,Dist[i]/2}); Dist[i]=INF; } } } return 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...