#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <iomanip>
const double INF = std::numeric_limits<double>::infinity();
struct State {
double time;
int country;
int div2_used;
bool operator>(const State& other) const {
return time > other.time;
}
};
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) {
std::vector<std::vector<std::pair<int, int>>> graph(N);
// Build the graph
for (int i = 0; i < M; ++i) {
graph[x[i]].emplace_back(y[i], c[i]);
graph[y[i]].emplace_back(x[i], c[i]);
}
// Priority queue for Dijkstra-like algorithm
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
pq.push({0, 0, 0});
// Distance table to store the minimum time to reach each country with a certain number of divide-by-2 used
std::vector<std::vector<double>> dist(N, std::vector<double>(K + 1, INF));
dist[0][0] = 0;
while (!pq.empty()) {
auto [current_time, current_country, div2_used] = pq.top();
pq.pop();
if (current_country == H) {
return current_time;
}
// Early exit if we already have found a better way
if (current_time > dist[current_country][div2_used]) {
continue;
}
// Explore all adjacent countries
for (const auto& [next_country, travel_time] : graph[current_country]) {
double next_time = current_time + travel_time;
// Case 1: Without using any special ability
if (next_time < dist[next_country][div2_used]) {
dist[next_country][div2_used] = next_time;
pq.push({next_time, next_country, div2_used});
}
// Case 2: Using special abilities
if (arr[next_country] == 0) {
next_time = 0;
if (next_time < dist[next_country][div2_used]) {
dist[next_country][div2_used] = next_time;
pq.push({next_time, next_country, div2_used});
}
} else if (arr[next_country] == 2 && div2_used < K) {
next_time = current_time / 2.0;
if (next_time < dist[next_country][div2_used + 1]) {
dist[next_country][div2_used + 1] = next_time;
pq.push({next_time, next_country, div2_used + 1});
}
}
}
}
return -1; // If we exhaust the priority queue and don't find a way to H
}
