Submission #1065795

#TimeUsernameProblemLanguageResultExecution timeMemory
1065795MuhammetCyberland (APIO23_cyberland)C++17
0 / 100
3106 ms1051292 KiB
#include <bits/stdc++.h> #include "cyberland.h" using namespace std; #define ff first #define ss second double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { vector <pair<int,int>> v[n+5]; for(int i = 0; i < m; i++){ v[x[i]].push_back({y[i],c[i]}); v[y[i]].push_back({x[i],c[i]}); } priority_queue <pair<double,pair<int,int>>> q; vector <double> dis(n+5,1e9); vector <int> dis1(n+5,k+1); dis[0] = 0; dis1[0] = 0; q.push({0,{0,0}}); while(!q.empty()){ auto [ind,kcur] = q.top().ss; double w = q.top().ff; q.pop(); if(w < 0) w *= (-1); dis1[ind] = min(dis1[ind],kcur); dis[ind] = min(dis[ind],w); if(h == ind) continue; double w2 = w; for(auto [i,j] : v[ind]){ w = w2; if(arr[i] == 0){ w = 0; if(dis[i] > 0){ q.push({0,{i,kcur}}); } } else if(arr[i] == 2){ w += j; if(kcur < k){ w /= 2; kcur++; if(dis[i] > w){ q.push({-w,{i,kcur}}); } kcur--; } w = w2; if(dis[i] > w){ q.push({-w,{i,kcur}}); } } else { w += j; if(w < dis[i]){ q.push({-w,{i,kcur}}); } } } } if(dis[h] == 1e9) return -1; return dis[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...