| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 982503 | ASGA_RedSea | 사이버랜드 (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double inf = 1e18;
const double err = 1e-7;
struct w{
int b,c;
};
w hi;
int n,m,k,h;
vector <int> a,v;
vector <double> d;
vector <vector <w>> g;
priority_queue <pair <double,pair <int,int>>> q;
bool check(int i){
v[i] = 1;
for(auto& j : g[i]){
if(v[j.b])continue;
if(j.b == h || check(j.b))return 1;
}
return 0;
}
double solve(int N,int M,int K,int H,vector <int> X,vector <int> Y,vector <int> C,vector <int> A){
n = N;m = M;k = K;h = H;a = A;
g.resize(n);
for(int i = 0;i < m;i++){
hi.b = Y[i];
hi.c = C[i];
g[X[i]].push_back(hi);
hi.b = X[i];
g[Y[i]].push_back(hi);
}
v = vector <int> (n,0);
if(check(0) == 0)return -1;
d = vector <double> (n,inf);
v = vector <int> (n,0);
d[0] = 0;
q.push({0,{0,0}});
while(!q.empty()){
pair <double,pair <int,int>> s = q.top();q.pop();
int i = s.second.second,ck = s.second.first;
for(auto& j : g[i]){
if(a[j.b] == 0){
if(d[j.b] <= err)continue;
d[j.b] = 0.00000000000;
if(v[j.b] == 0 && j.b != h){q.push({0.00000000,{ck,j.b}});v[j.b]++;}
}
else{
if(a[j.b] == 2 && ck < k){
if(d[j.b] - ((d[i] + j.c) / 2.0000000) > err){
d[j.b] = ((d[i] + j.c) / 2.00000000);
if(v[j.b] == 0 && j.b != h){q.push({-d[j.b],{ck + 1,j.b}});v[j.b]++;}
}
}
if((d[j.b] - (d[i] + j.c)) <= err)continue;
d[j.b] = (d[i] + j.c);
if(v[j.b] == 0 && j.b != h){q.push({-d[j.b],{ck,j.b}});v[j.b]++;}
}
}
}
return d[h];
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie();
int n,m,k,h;cin >> n >> m >> k >> h;
vector <int> x(m),y(m),c(m),arr(n);
for(auto& i : x)cin >> i;
for(auto& i : y)cin >> i;
for(auto& i : c)cin >> i;
for(auto& i : arr)cin >> i;
cout << fixed << setprecision(6) << solve(n,m,k,h,x,y,c,arr) << '\n';
return 0;
}