제출 #794539

#제출 시각아이디문제언어결과실행 시간메모리
794539FEDIKUS사이버랜드 (APIO23_cyberland)C++17
44 / 100
332 ms74420 KiB
#include "cyberland.h" #include <bits/stdc++.h> using ll = long long; using namespace std; const double eps=1e-8; const int maxn=1e5+10; const double inf=1e15; const int maxk=110; int n,m,k,h; vector<pair<int,int> > g[maxn]; ll dist[maxn][maxk]; bool bio[maxn]; void dfs(int node){ if(bio[node]) return; bio[node]=true; for(auto [i,c]:g[node]){ if(bio[i]) continue; dfs(i); } } double solve(int _n,int _m,int _k, int _h,vector<int> x,vector<int> y,vector<int> c,vector<int> arr){ n=_n; m=_m; k=_k; h=_h; k=min(k,100); for(int i=0;i<n;i++) g[i].clear(); for(int i=0;i<n;i++) bio[i]=false; for(int i=0;i<n;i++) for(int j=0;j<=k;j++) dist[i][j]=inf; for(int i=0;i<m;i++){ if(x[i]==h || y[i]==h) continue; g[x[i]].push_back({y[i],c[i]}); g[y[i]].push_back({x[i],c[i]}); } dfs(0); bool moze=false; for(int i=0;i<m;i++){ if(x[i]==h || y[i]==h){ if(bio[x[i]] || bio[y[i]]) moze=true; } } if(!moze) return -1; priority_queue<tuple<ll,int,int> > pq; pq.push({0,0,0}); dist[0][0]=0; for(int i=0;i<n;i++){ if(arr[i]==0 && bio[i]){ pq.push({0,i,0}); dist[i][0]=0; } } while(!pq.empty()){ auto [cost,node,delio]=pq.top(); pq.pop(); cost=-cost; if(cost>dist[node][delio]/*-eps*/) continue; for(auto [i,c]:g[node]){ if(arr[i]==2){ if(cost+c<dist[i][delio]/*-eps*/){ dist[i][delio]=cost+c; pq.push({-dist[i][delio],i,delio}); } if(delio<k && 2*(cost+c)<dist[i][delio+1]/*-eps*/){ dist[i][delio+1]=(cost+c)/2; pq.push({-dist[i][delio+1],i,delio+1}); } }else{ if(cost+c<dist[i][delio]/*-eps*/){ dist[i][delio]=cost+c; pq.push({-dist[i][delio],i,delio}); } } } } ll ret=inf; for(int i=0;i<m;i++){ if(x[i]==h || y[i]==h){ if(x[i]!=h) for(int j=0;j<=k;j++) ret=min(ret,dist[x[i]][j]+c[i]); if(y[i]!=h) for(int j=0;j<=k;j++) ret=min(ret,dist[y[i]][j]+c[i]); } } return ret; }
#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...