Submission #1193414

#TimeUsernameProblemLanguageResultExecution timeMemory
1193414yuichiro17Cyberland (APIO23_cyberland)C++20
15 / 100
956 ms2162688 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; using ld = long double; const ld inf = numeric_limits<ld>::max(); 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) { vector<vector<pair<int,int>>> adj(N); for(int i=0;i<M;i++){ adj[x[i]].push_back({y[i],c[i]}); adj[y[i]].push_back({x[i],c[i]}); } vector<vector<ld>> v(N,vector<ld>(K,inf)); v[0][0]=0; queue<pair<int,int>> q; q.push({0,0}); while(!q.empty()){ pair<int,int> current = q.front(); q.pop(); for(pair<int,int> p:adj[current.first]){ if(arr[p.first]==0&&v[p.first][current.second]!=0){ v[p.first][current.second]=0; q.push({p.first,current.second}); }else if(v[current.first][current.second]+p.second<v[p.first][current.second]){ v[p.first][current.second]=v[current.first][current.second]+p.second; q.push({p.first,current.second}); }else if(current.second!=K-1&&arr[p.first]==2){ if(v[current.first][current.second]+p.second<2*v[p.first][current.second+1]){ v[p.first][current.second+1]=(ld)(v[current.first][current.second]+p.second)/2; q.push({p.first,current.second+1}); } } } } ld ans=inf; for(int i=0;i<K;i++){ ans = min(ans,v[H][i]); } return (ans==inf?-1: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...