제출 #957541

#제출 시각아이디문제언어결과실행 시간메모리
957541zeta7532사이버랜드 (APIO23_cyberland)C++17
15 / 100
287 ms9312 KiB
#include "cyberland.h" #include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; using ll = int; using P = pair<double,int>; const ll mod = 998244353; #define fi first #define se second #define rep(i,n) for(ll i=0;i<n;i++) #define all(x) x.begin(),x.end() #define faster ios::sync_with_stdio(false);cin.tie(nullptr) 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<double> dis(N,1e15); double ans=1e15; dis[0]=0; vector<vector<pair<int,int>>> G(N); rep(i,M){ G[x[i]].push_back({y[i],i}); G[y[i]].push_back({x[i],i}); } rep(loop,100){ priority_queue<P,vector<P>,greater<P>> pq; rep(i,N) pq.emplace(dis[i],i); while(!pq.empty()){ P p=pq.top(); pq.pop(); int v=p.se; if(p.fi>dis[v]) continue; if(p.fi==1e15) continue; for(auto &e:G[v]){ double cost=dis[v]+c[e.se]; if(arr[e.fi]==0) cost=0; if(arr[e.fi]==2) continue; if(dis[e.fi]>cost){ dis[e.fi]=cost; pq.emplace(dis[e.fi],e.fi); } } } ans=min(ans,dis[H]); dis[H]=1e15; if(loop==K) break; vector<double> next_dis(N,1e15); rep(i,M){ if(arr[x[i]]==2) if(dis[y[i]]<1e15) next_dis[x[i]]=min(next_dis[x[i]],(dis[y[i]]+c[i])/2); if(arr[y[i]]==2) if(dis[x[i]]<1e15) next_dis[y[i]]=min(next_dis[y[i]],(dis[x[i]]+c[i])/2); } rep(i,N){ dis[i]=min(dis[i],next_dis[i]); } } if(ans==1e15) 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...