#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]; }