#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);
}
}
/*
Idea: Dijkstra's algorithm
priority_queue<{total_time, node}>
*/
double ans = numeric_limits<double>::max();
priority_queue<pair<double, node>, vector<pair<double, node>>, greater<pair<double, node>>> q;
for(int k = 0; k <= K; k++) {
q.push({0.0, {0, k}});
for(int i = 1; i < N; i++) {
if(arr[i] == 0 && found[i]) {
q.push({0.0, {i, k}});
}
}
}
vector<bool> vis((N << 5) | K, false);
while(! q.empty()) {
auto [cur_time, cur_node] = q.top();
q.pop();
if(vis[cur_node.get_ind()]) continue;
vis[cur_node.get_ind()] = true;
auto [i, k] = cur_node;
if(i == H) {
ans = min(ans, cur_time);
continue;
}
for(auto [j, w] : adj[i]) {
if(arr[j] == 0) {
q.push({0.0, {j, k}});
} else if(arr[j] == 1) {
q.push({cur_time + (double)w, {j, k}});
} else {
q.push({(cur_time + (double)w) / 2.0, {j, k + 1}});
}
}
if(arr[i] == 2 && k <= K) {
for(auto [j, w] : adj[i]) {
q.push({cur_time / 2.0 + (double)w, {j, k + 1}});
}
}
}
if(ans < numeric_limits<double>::max()) {
return ans;
}
return -1;
}
