#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const double inf = 1e18;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
double ans = 1e18;
K = min(K, 100);
vector<pair<int,int>> adj[N];
vector<double> dp(N, inf), tmp(N, inf);
for(int i = 0;i < M; i++){
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
priority_queue<pair<double, int>> pq;
tmp[0] = 0.0;
for(int i = 0; i <= K; i++){
if(i){
for(int j = 0; j < N; j++){
if(arr[i] == 1 || dp[i] == inf) continue;
if(arr[i] == 0) tmp[i] = 0.0;
pq.push({-dp[i]/2.0, i});
}
}else pq.push({0.0, 0});
while(!pq.empty()){
auto [c, u] = pq.top(); pq.pop();
c = -c;
if(u == H) continue;
if(c > dp[u]) continue;
for(auto &[v, w] : adj[u]){
double cost = c+w;
if(tmp[v] > cost){
if(arr[i] == 0) tmp[v] = 0.0;
else tmp[v] = cost;
pq.push({-tmp[v], v});
}
}
}
ans = min(ans, tmp[H]);
if(i == 0 && tmp[H]== inf) break;
swap(tmp, dp);
}
return (ans >= inf/2 ? -1.0 :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... |