#include "cyberland.h"

#include <vector>
#include <set>
#include <iostream>

using namespace std;

const long long INF = (long long) 1e18;

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) {
    long double dp[N][K + 1];
    for(int i = 0; i < N; i++){
        for(int j = 0; j <= K; j++)
            dp[i][j] = INF;
    }
    set<pair<long double, pair<int, int>>> st;
    vector<pair<int, int>> g[N];
    for(int i = 0; i < M; i++){
        g[x[i]].emplace_back(y[i], c[i]);
        g[y[i]].emplace_back(x[i], c[i]);
    }
    for(int i = 0; i < N; i++){
        if(arr[i] == 0){
            dp[i][0] = 0;
            st.insert({0, {i, 0}});
        }
    }
    dp[0][0] = 0;
    st.insert({0, {0, 0}});
    while(!st.empty()){
        auto pr = *st.rbegin();
        st.erase(pr);
        int v = pr.second.first, j = pr.second.second;
        if(v == H) continue;
        for(auto p : g[v]){
            int u = p.first, c = p.second;
            if(dp[u][j] > dp[v][j] + c){
                st.erase({dp[u][j], {u, j}});
                dp[u][j] = dp[v][j] + c;
                st.insert({dp[u][j], {u, j}});
            }
            if(arr[u] == 2 && j + 1 <= K && dp[u][j + 1] > (dp[v][j] + c) / 2){
                st.erase({dp[u][j + 1], {u, j + 1}});
                dp[u][j + 1] = (dp[v][j] + c) / 2;
                st.insert({dp[u][j + 1], {u, j + 1}});
            }
            if(arr[v] == 1 && j + 1 <= K && dp[u][j + 1] > dp[v][j] / 2 + c){
                st.erase({dp[u][j + 1], {u, j + 1}});
                dp[u][j + 1] = dp[v][j] / 2 + c;
                st.insert({dp[u][j + 1], {u, j + 1}});
            }
        }
    }
    long double res = INF;
    for(int j = 0; j <= K; j++)
        res = min(res, dp[H][j]);
    return res;
}