#include <bits/stdc++.h>
#include "cyberland.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e5+10;
const int MAXK = 35;
const double INF = 1e16+10;
const ll MOD = 1e9 + 7;
const ll LOG = 20;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
int n, m, k, h;
int ty[MAXN];
double dp[MAXK][MAXN];
vector <pii> vec;
vector <pii> adj[MAXN];
bool dfs(int nw, int par){
if(nw == h) return 1;
bool ada = 0;
for(auto ed : adj[nw]){
int nx = ed.fi; int wei = ed.se;
if(nx == par) continue;
if(!dfs(nx, nw)) continue;
vec.pb(pii(nw, wei)); //nw-nx = wei
ada = 1;
}
return ada;
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
n = N; m = M; k = K; h = H;
for(int i=0; i<=m-1; i++){
adj[x[i]+1].pb(pii(y[i]+1, c[i])); adj[y[i]+1].pb(pii(x[i]+1, c[i]));
}
for(int i=0; i<n; i++) ty[i+1] = arr[i];
//dji();
int en = h-1; int sta = 0;
for (int i=en;i>=0;i--) {
if (arr[i] == 0) {
sta = i;
break;
}
}
/*for(auto in : vec)cout << in.fi << ' ' << in.se << "in\n";
cout << sta << ' ' << en << "sta\n";
return 0;*/
for(int i=sta; i<=en; i++){ //idx = sta-en
for(int j=0; j<=k; j++) dp[j][i] = INF;
}
dp[0][sta] = 0;
for(int j=0; j<=k; j++){
for(int i=sta; i<=en; i++){
double te1 = INF, te2 = INF, las = INF;
if(sta < i && arr[i]==2 && j!=0) te1 = (dp[j-1][i-1]+c[i-1])/2;
if(i < en && arr[i]==2 && j!=0) te2 = (dp[j-1][i+1]+c[i])/2;
dp[j][i] = min(min(te1, te2), min(las, dp[j][i]));
}
for(int i=sta+1; i<=en; i++){
dp[j][i] = min(dp[j][i], dp[j][i-1]+c[i-1]);
}
for(int i=en-1; i>=sta; i--){
dp[j][i] = min(dp[j][i], dp[j][i+1]+c[i]);
}
}
/*for(int i=sta; i<=en; i++){
for(int j=0; j<=k; j++) cout << dp[i][j] << ' ';
cout << '\n';
}*/
double ans = INF;
for(int i=0; i<=k; i++) ans = min(ans, dp[i][en]);
return ans+c[en];
}
