#include <vector>
#include <queue>
#include <limits>
using namespace std;
struct Node {
int country;
int time;
Node(int c, int t) : country(c), time(t) {}
bool operator>(const Node& other) const {
return time > other.time;
}
};
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<pair<int, int>>> graph(N);
for (int i = 0; i < M; ++i) {
graph[x[i]].push_back({y[i], c[i]});
graph[y[i]].push_back({x[i], c[i]});
}
priority_queue<Node, vector<Node>, greater<Node>> pq;
vector<int> dist(N, numeric_limits<int>::max());
pq.push(Node(0, 0));
dist[0] = 0;
int divide_by_2_used = 0;
while (!pq.empty()) {
Node current = pq.top();
pq.pop();
int country = current.country;
int time = current.time;
if (country == H) return time;
if (divide_by_2_used >= K) continue;
for (auto neighbor : graph[country]) {
int next_country = neighbor.first;
int next_time = time + neighbor.second;
if (arr[next_country] == 2) {
next_time /= 2; // Divide-by-2 ability
divide_by_2_used++; // Increment divide_by_2 counter
} else if (arr[next_country] == 0) {
next_time = 0; // Passing time is 0
}
if (next_time < dist[next_country]) {
dist[next_country] = next_time;
pq.push(Node(next_country, next_time));
}
}
}
return -1;
}
