Submission #1202590

#TimeUsernameProblemLanguageResultExecution timeMemory
1202590Francisco_MartinCyberland (APIO23_cyberland)C++20
20 / 100
3100 ms526140 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; #define debug(x) cerr<<#x" = "<<x<<"\n"; #define debugv(x) cerr<<#x" = [ "; for(auto v:x) cerr << v << ", "; cerr<<"]\n"; using ll=long long; using ld=double; const ld INF=1e18; double solve(int N,int M,int K,int H,vector<int> x,vector<int> y,vector<int> c,vector<int> arr){ K=min(K,70); ld ans=INF; vector<vector<ld>> A(K+1,vector<ld>(N,INF)); vector<pair<ll,ld>> g[N]; priority_queue<pair<ld,ll>> pq; 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]}); } A[0][0]=0; for(int i=0; i<=K; i++){ for(int j=0; j<N; j++) if(A[i][j]!=INF) pq.push({-A[i][j],j}); while(!pq.empty()){ auto [w,v]=pq.top(); pq.pop(); if(A[i][v]<-w || v==H) continue; for(auto [u,w2]:g[v]){ if(arr[u]==0){ A[i][u]=0; pq.push({0,u}); }else if(A[i][u]>-w+w2){ A[i][u]=-w+w2; pq.push({w-w2,u}); } if(arr[u]==2 && i!=K && A[i+1][u]>(-w+w2)/2) A[i+1][u]=(-w+w2)/2; } } } for(int i=0; i<=K; i++) ans=min(ans,A[i][H]); if(ans==INF) return -1; else return ans; }
#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...