이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#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;
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);
}
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) > err){
d[j.b] = ((d[i] + j.c) / 2);
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 (abs(d[h] - inf) <= err ? -1 : d[h]);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |