#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
struct kek {
double dist;
int node;
int cnt;
};
bool operator < (const kek &a, const kek &b) {
return a.dist > b.dist;
}
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, 100);
vector<vector<pair<int, int>>> g(n);
vector<int> t(n);
iota(all(t), 0);
auto root = [&](auto self, int x) {
if (x == t[x]) return x;
return t[x] = self(self, t[x]);
};
auto join = [&](int x, int y) -> void {
x = root(root, x), y = root(root, y);
t[x] = y;
};
for (int i = 0; i < m; i++) {
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
join(x[i], y[i]);
}
if (root(root, 0) != root(root, h)) {
return -1;
}
priority_queue<kek> pq;
vector<vector<double>> dist(n, vector<double>(k + 1, 1e18));
for (int i = 0; i < n; i++) {
if (i == 0) {
dist[i][0] = 0;
pq.push({0, i, 0});
}
}
while (!pq.empty()) {
int u = pq.top().node;
int kk = pq.top().cnt;
pq.pop();
if (u == h) continue;
for (auto [v, c] : g[u]) {
if (dist[u][kk] + c < dist[v][kk]) {
dist[v][kk] = dist[u][kk] + c;
if (arr[v] == 0) dist[v][kk] = 0;
pq.push({dist[v][kk], v, kk});
}
if (v != h && arr[v] == 2 && kk + 1 <= k && (dist[u][kk] + c) / 2 < dist[v][kk + 1]) {
dist[v][kk + 1] = (dist[u][kk] + c) / 2;
pq.push({dist[v][kk + 1], v, kk + 1});
}
}
}
double res = 1e18;
for (int i = 0; i <= k; i++) res = min(res, dist[h][i]);
return res;
}
# | 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... |