/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include "cyberland.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using db = double;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif
int _n, _m, _k, _h;
db ans;
vector<char> used;
vector<db> dp;
vector<int> X, Y, C, A;
vector<vector<pair<int, db>>> g;
inline void systemd() {
ans = -1;
used.assign(_n, false);
dp.clear();
g.clear();
g.resize(_n);
for (int _ = 0; _ < _m; _++) {
const int &u = X[_], &v = Y[_], w = C[_];
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
}
}
void dfs_1(int v = 0) {
used[v] = true;
if (v == _h)
return;
for (const auto &[u, w] : g[v]) {
if (used[u])
continue;
dfs_1(u);
}
}
struct node {
db cur;
int v, k;
char operator>(const node &x) {
if (x.cur == cur) {
return x.k > k;
}
return x.cur > cur;
}
char operator<(const node &x) {
if (x.cur == cur) {
return x.k < k;
}
return x.cur < cur;
}
};
void dijikstra(vector<int> st = {-1}) {
priority_queue<pair<db, int>, vector<pair<db, int>>, greater<>> pq;
dbg("s");
dbg(st);
if (st[0] == -1) {
for (int v = 0; v < _n; v++) {
if (dp[v] != INFll) {
pq.push({0, v});
}
}
} else {
dbg(st);
for (int v : st) {
pq.push({dp[v], v});
}
dbg(st);
}
while (!pq.empty()) {
auto [dst, v] = pq.top();
pq.pop();
if (v == _h)
continue;
dbg(v);
dbg(dst);
for (const auto &[u, w] : g[v]) {
if ((db)dst + w < dp[u]) {
dp[u] = dst + w;
pq.push({(db)dst + w, u});
}
}
}
}
char solve() {
systemd();
dfs_1();
if (!(used[_h]))
return 0;
dp.assign(_n, INFll);
dp[0] = 0;
for (int v = 0; v < _n; v++) {
if (A[v] == 0 && used[v]) {
dp[v] = 0;
}
}
dijikstra();
dbg(dp);
ans = INFll;
ans = min(ans, dp[_h]);
dbg(ans);
_k = min(_k, 100);
for (int k = 0; k < _k; k++) {
vector<db> ndp(_n, INFll);
vector<int> st;
for (int v = 1; v < _n; v++) {
if (!used[v])
continue;
if (v == _h)
continue;
for (const auto &[u, w] : g[v]) {
db nxt = INFll;
if (!used[u])
continue;
if (A[u] == 2) {
nxt = ((db)(dp[v] + (db)w) / 2.0);
} else {
continue;
}
if (nxt < ndp[u]) {
ndp[u] = nxt;
st.push_back(u);
}
}
}
for (int v = 0; v < _n; v++) {
dp[v] = min(dp[v], ndp[v]);
}
// dp.swap(ndp);
dbg(dp);
dbg(ans);
if (st.empty()) {
break;
}
dijikstra(st);
}
ans = min(ans, dp[_h]);
dbg(ans);
return 0;
}
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) {
_n = N, _m = M, _k = K, _h = H;
X = x, Y = y, C = c, A = arr;
x.clear(), y.clear(), c.clear(), arr.clear();
assert(!solve());
return ans;
}
// Attack on titan<3
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
1
4 4 30 3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4
1
3 2 30 2
1 2 1
1 2 12
2 0 4
2
5 0 30 4
1 1 1 1 1
5 0 30 0
1 1 1 1 1
/// XXX: Bug:0 was not stoped at dfs(_h)
1
5 5 30 4
1 1 0 1 0
1 2 1
2 3 1
1 3 1
3 4 1
4 5 1
/// XXX: We have another bug when arr[i] == 2 apears
_______________
1
5 4 30 4
1 2 2 1 1
0 1 2
1 2 2
2 3 2
3 4 2
*/
