제출 #1193412

#제출 시각아이디문제언어결과실행 시간메모리
1193412yuichiro17Cyberland (APIO23_cyberland)C++20
8 / 100
1049 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; }
#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...