| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 940653 | PenguinsAreCute | 사이버랜드 (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cyberland_apio23.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define pb emplace_back
#define fi first
#define se second
using di = pair<double,int>;
vector<pair<int,double>> adj[121010];
double dist[121010];
void distra(int N) { // i use jk 4 esc on nvim
priority_queue<di,vector<di>,greater<di>> pq;
REP(i,0,N) dist[i]=-1;
dist[N]=0;
pq.push(di(0,N));
while(pq.size()) {
di x = pq.top(); pq.pop();
if(abs(x.fi-dist[x.se]) > 1e-5) continue;
for(auto i: adj[x.se]) if(dist[i.fi]<-0.5||dist[i.fi]>x.fi+i.se) {
dist[i.fi]=x.fi+i.se;
pq.push(di(dist[i.fi],i.fi));
}
}
}
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) {
K=min(K,70);
double ans = 1e15;
REP(i,0,N+1) adj[i].clear();
REP(i,0,M) {
if(x[i]!=H) adj[x[i]].pb(y[i],c[i]);
if(y[i]!=H) adj[y[i]].pb(x[i],c[i]);
}
adj[N].pb(0,0);
distra(N);
REP(i,0,N) if(!arr[i] && dist[i]>-0.5) adj[N].pb(i,0);
REP(i,0,K+1) {
distra(N);
if(dist[H]>-0.5) ans=min(ans,dist[H]);
adj[N].clear();
REP(i,0,N) if(arr[i]==2) {
double nxtDist = 1e15;
for(auto j: adj[i]) if(j.fi!=H&&dist[j.fi]>-0.5) nxtDist=min(nxtDist,dist[j.fi]+j.se);
if(nxtDist<9e14) adj[N].pb(i,nxtDist/2.0);
}
}
return (ans>=9e14?-1:ans);
}