Submission #771919

#TimeUsernameProblemLanguageResultExecution timeMemory
771919Tenis0206Cyberland (APIO23_cyberland)C++17
0 / 100
3049 ms26000 KiB
#include <bits/stdc++.h> using namespace std; const int nmax = 1e5; const int kmax = 30; const int oo = INT_MAX; int n,m,k,f; int tip[nmax + 5]; double d[nmax + 5][kmax + 5]; bool sel[nmax + 5][kmax + 5]; vector<pair<int,int>> G[nmax + 5]; vector<int> l; typedef pair<int,pair<int,int>> pi; void add_zero(int nod) { sel[nod][0] = true; if(tip[nod]==0) { l.push_back(nod); } if(nod==f) { return; } for(auto it : G[nod]) { if(sel[it.first][0]) { continue; } add_zero(it.first); } } void Dijkstra() { priority_queue <pi,vector<pi>,greater<pi>> h; for(int i=0;i<n;i++) { for(int p=0;p<=k;p++) { d[i][p] = oo; sel[i][p] = false; } } d[0][0] = 0; h.push({0,{0,0}}); l.clear(); add_zero(0); if(!sel[f][0]) { d[f][0] = -1; return; } for(int i=0;i<n;i++) { sel[i][0] = false; } for(auto it : l) { d[it][0] = 0; h.push({0,{it,0}}); } while(!h.empty()) { while(!h.empty() && sel[h.top().second.first][h.top().second.second]) { h.pop(); } if(h.empty()) { return; } int nod = h.top().second.first; int nr = h.top().second.second; h.pop(); sel[nod][nr] = true; if(nod==f) { continue; } for(auto it : G[nod]) { double new_t = d[nod][nr] + it.second; if(tip[it.first]==0) { continue; } if(new_t < d[it.first][nr]) { d[it.first][nr] = new_t; h.push({d[it.first][nr],{it.first,nr}}); } if(tip[it.first]==2 && nr < k) { if(new_t * 0.5 < d[it.first][nr + 1]) { d[it.first][nr+1] = new_t * 0.5; h.push({d[it.first][nr+1],{it.first,nr+1}}); } } } if(tip[nod]==2 && nr < k) { double new_t = (d[nod][nr] + 2) * 0.5; if(new_t < d[nod][nr + 1]) { d[nod][nr + 1] = new_t; h.push({d[nod][nr+1],{nod,nr+1}}); } } } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { n = N, m = M, k = K, f = H; for(int i=0;i<m;i++) { G[x[i]].push_back({y[i],c[i]}); G[y[i]].push_back({x[i],c[i]}); } for(int i=0;i<n;i++) { tip[i] = arr[i]; } Dijkstra(); double rez = oo; for(int p=0;p<=k;p++) { rez = min(rez, d[f][p]); } return rez; }
#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...