Submission #1202608

#TimeUsernameProblemLanguageResultExecution timeMemory
1202608AlmontherCyberland (APIO23_cyberland)C++20
5 / 100
926 ms22084 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define co cout<< // stuff 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){ K=min(K,70); double vis[N+5][K+5]={}; double ans=1e9; for(int i=0;i<=N;i++) for(int j=0;j<=K;j++) vis[i][j]=ans; vector<pair<double,int>>v[N+5]; for(int i=0;i<M;i++){ v[x[i]].push_back({c[i],y[i]}); v[y[i]].push_back({c[i],x[i]}); } priority_queue<pair<double,int>>q[K+5]; q[K].push({0,0}); for(int i=K;i>=0;i--){ while(q[i].size()){ auto[wei,idx]=q[i].top(); wei=-wei; q[i].pop(); if(vis[idx][i]<=wei) continue; vis[idx][i]=wei; if(idx==H){ ans=min(ans,wei); continue; } for(auto[wei1,idx1]:v[idx]){ if(arr[idx]==0) q[i].push({-wei1,idx1}); else if(arr[idx]==2&&i>0) q[i-1].push({-(wei/2+wei1),idx1}); q[i].push({-(wei+wei1),idx1}); } } } if(ans==1e9) return -1; 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...