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