#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define co cout<<
// stuff
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 vis[N+5][K+5]={};
double ans=1e9;
for(int i=0;i<=N;i++) for(int j=0;j<=K;j++) vis[i][j]=ans;
vector<pair<double,int>>v[N+5];
for(int i=0;i<M;i++){
v[x[i]].push_back({c[i],y[i]});
v[y[i]].push_back({c[i],x[i]});
}
priority_queue<pair<double,int>>q[K+5];
q[K].push({0,0});
for(int i=K;i>=0;i--){
while(q[i].size()){
auto[wei,idx]=q[i].top();
wei=-wei;
q[i].pop();
if(vis[idx][i]<=wei) continue;
vis[idx][i]=wei;
if(idx==H){
ans=min(ans,wei);
continue;
}
for(auto[wei1,idx1]:v[idx]){
if(arr[idx]==0) q[i].push({-wei1,idx1});
else if(arr[idx]==2&&i>0) q[i-1].push({-(wei/2+wei1),idx1});
q[i].push({-(wei+wei1),idx1});
}
}
}
if(ans==1e9) 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... |