#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});
}
/*
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;
q.push({0.0, {0, 0}});
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;
}
if(arr[i] == 0) {
for(auto [j, w] : adj[i]) {
q.push({(double)w, {j, k}});
}
} else {
for(auto [j, w] : adj[i]) {
q.push({cur_time + (double)w, {j, k}});
}
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;
}
