#include "cyberland.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
struct node {
int i;
int k;
node(int a_i, int a_k): i(a_i), k(a_k) {};
int get_ind() {
return (i << 5) | k;
}
bool operator<(const node& other) const {
return true;
}
};
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) {
vector<vector<pair<int, int>>> adj;
for(int i = 0; i < N; i++) {
vector<pair<int, int>> adj_row;
adj.push_back(adj_row);
}
for(int i = 0; i < M; i++) {
int curx = x[i], cury = y[i], curc = c[i];
adj[curx].push_back({cury, curc});
adj[cury].push_back({curx, curc});
}
/*
Initial BFS to find the reachable nodes
*/
vector<bool> found(N, false);
queue<int> bfs_q;
bfs_q.push(0);
while(!bfs_q.empty()) {
int curq = bfs_q.front();
bfs_q.pop();
if(found[curq]) continue;
found[curq] = true;
for(auto [j, w] : adj[curq]) {
bfs_q.push(j);
}
}
if(!found[H]) return -1;
/*
Idea: Dijkstra's algorithm
priority_queue<{total_time, node}>
*/
double ans = numeric_limits<double>::max();
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
vector<double> dist(N, 0.0);
for(int k = 0; k <= K; k++) {
vector<bool> vis(N, false);
if(k == 0) {
q.push({0.0, 0});
for(int i = 1; i < N; i++) {
if(arr[i] == 0 && found[i]) {
q.push({0.0, i});
}
}
} else {
q.push({0.0, 0});
for(int i = 1; i < N; i++) {
if(arr[i] == 0 && found[i]) {
q.push({0.0, i});
}
if(arr[i] == 2 && found[i]) {
double min_i_time = numeric_limits<double>::max();
for(auto [j, w] : adj[i]) {
min_i_time = min(min_i_time, dist[j] + (double)w);
}
q.push({min_i_time / 2.0, i});
}
}
}
while(! q.empty()) {
auto [cur_time, i] = q.top();
q.pop();
if(vis[i]) continue;
vis[i] = true;
dist[i] = cur_time;
if(i == H) {
ans = min(ans, cur_time);
continue;
}
for(auto [j, w] : adj[i]) {
if(arr[j] == 1 || arr[j] == 2) {
q.push({cur_time + (double)w, j});
}
}
}
}
return ans;
}
