| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 957909 | MtSaka | 사이버랜드 (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cyberland.h"
#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,l,r) for(ll i=(ll)l;i<(ll)r;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
static constexpr ll inf=numeric_limits<ll>::max()/2;
using vl=vector<ll>;
using ld=long double;
static constexpr ld eps=1e-8;
struct UnionFind{
private:
vector<int>par;
public:
UnionFind(int n):par(n,-1){}
int root(int v){return par[v]<0?v:par[v]=root(par[v]);}
bool same(int u,int v){return root(u)==root(v);}
bool merge(int u,int v){
u=root(u),v=root(v);
if(u==v)return false;
if(par[u]>par[v])swap(u,v);
par[u]+=par[v];
par[v]=u;
return true;
}
};
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){
chmin(K,100);
vector<vector<ld>>dist(N,vector<ld>(K+1,inf));
vector<vector<pair<ll,ll>>>g(N);
UnionFind uf(N);
rep(i,M){
g[x[i]].eb(y[i],c[i]);
g[y[i]].eb(x[i],c[i]);
uf.merge(x[i],y[i]);
}
priority_queue<tuple<ld,ll,ll>,vector<tuple<ld,ll,ll>>,greater<>>pq;
rep(i,N){
if(uf.same(0,i)&&(i==0||arr[i]==0)){
dist[i][K]=0;
pq.emplace(0,i,K);
}
}
for(int i=0;i<=K;++i){
priority_queue<tuple<ld,ll,ll>,vector<tuple<ld,ll,ll>>,greater<>>npq;
while(!pq.empty()){
auto [d,v,k]=pq.top();pq.pop();
if(d-dist[v][k]>eps)continue;
if(v==H)continue;
for(auto [u,cost]:g[v]){
if(dist[u][k]-(ld)(d+cost)>eps){
dist[u][k]=(ld)(d+cost);
pq.emplace(dist[u][k],u,k);
}
if(k-1>=0&&arr[u]==2&&dist[u][k-1]-(ld(d+cost)/2.0)>eps){
dist[u][k-1]=(ld)(d+cost)/2.0;
npq.emplace(dist[u][k-1],u,k-1);
}
}
}
pq=move(npq);
}
ld res=inf;
rep(i,K+1)chmin(res,dist[H][i]);
if(res==inf)return -1;
return res;
}
int main(){
cout<<solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});
}