#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
// Initialize the priority queue to store (time, country) pairs
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// Initialize the distance array with infinity
vector<int> dist(N, INF);
// Start from your country (country 0)
pq.push({0, 0});
dist[0] = 0; // Time to reach your country is 0
// Dijkstra's algorithm
while (!pq.empty()) {
int curr_time = pq.top().first;
int curr_country = pq.top().second;
pq.pop();
// If we reached Cyberland, return the time
if (curr_country == H) return curr_time;
// Iterate over neighboring countries
for (int i = 0; i < M; ++i) {
if (x[i] == curr_country || y[i] == curr_country) {
int next_country = (x[i] == curr_country) ? y[i] : x[i];
int time_to_next = c[i];
// Apply special abilities if available
if (arr[curr_country] == 2 && K > 0) {
time_to_next /= 2;
--K; // Reduce the number of times we can use divide-by-2 ability
}
if(arr[curr_country] == 0) {
time_to_next = 0;
}
// Update the time to reach the neighboring country if needed
if (curr_time + time_to_next < dist[next_country]) {
dist[next_country] = curr_time + time_to_next;
pq.push({dist[next_country], next_country});
}
}
}
}
// If Cyberland is unreachable, return -1
return -1;
}
