#include <vector>
#include <queue>
#include <limits>
using namespace std;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<double> distances(N, numeric_limits<double>::infinity());
distances[0] = 0;
// Priority queue to store (distance, node)
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
pq.push({0, 0});
// Main Dijkstra's algorithm loop
while (!pq.empty()) {
double dist = pq.top().first;
int node = pq.top().second;
pq.pop();
// Check if we've reached Cyberland
if (node == H) {
return dist;
}
// Check if the current node has the divide-by-2 ability
if (arr[node] == 2 && K > 0) {
// Consider using the divide-by-2 ability
double new_dist = dist / 2.0;
// If using the ability leads to a shorter path, update distance
if (new_dist < distances[node]) {
distances[node] = new_dist;
// Push the updated distance to the priority queue
pq.push({new_dist, node});
// Decrement the remaining uses of divide-by-2 ability
K--;
}
}
// Iterate through neighbors of the current node
for (int i = 0; i < M; i++) {
int neighbor;
if (x[i] == node) {
neighbor = y[i];
} else if (y[i] == node) {
neighbor = x[i];
} else {
continue;
}
// Calculate the new distance to the neighbor
double new_dist = dist + c[i];
// Update the distance if it's shorter
if (new_dist < distances[neighbor]) {
distances[neighbor] = new_dist;
pq.push({new_dist, neighbor});
}
}
}
// If Cyberland is not reachable
return -1;
}
