이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "cyberland.h"
// #include "stub.cpp"
using namespace std;
#define lb long double
#define ll long long
#define ff first
#define ss second
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
vector <pair<ll, ll>> v[n+5];
ll s = 0;
for(auto i : c){
s += i;
}
s = log2(s);
k = min(k,(int)s+20);
k = min(k,60);
for(int i = 0; i < m; i++){
v[x[i]].push_back({y[i],c[i]});
v[y[i]].push_back({x[i],c[i]});
}
priority_queue <pair<lb,pair<ll,ll>>> q;
q.push({0,{0,0}});
vector <vector<lb>> dis(n+1, vector<lb> (k+1,1e18));
dis[0][0] = 0;
lb ans = 1e18;
bool tr = 0;
while(!q.empty()){
auto [w,x] = q.top();
q.pop();
w *= -1;
if(w != dis[x.ff][x.ss]) continue;
if(x.ff == h){
tr = 1;
ans = min(ans,w);
continue;
}
for(auto [to,w1] : v[x.ff]){
if(a[to] == 2 and x.ss < k){
lb w2 = w1;
if((dis[x.ff][x.ss] + w2) / 2 < dis[to][x.ss+1]){
dis[to][x.ss+1] = (dis[x.ff][x.ss] + w2) / 2;
q.push({-dis[to][x.ss+1],{to,x.ss+1}});
}
}
if((dis[to][x.ss] > dis[x.ff][x.ss] + w1) or (a[to] == 0 and dis[to][x.ss] != 0)){
dis[to][x.ss] = dis[x.ff][x.ss] + w1;
if(a[to] == 0) dis[to][x.ss] = 0;
q.push({-dis[to][x.ss],{to,x.ss}});
}
}
}
if(tr == 0) return -1;
return ans;
}
# | 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... |