#include "cyberland.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
const double INF = 1e18;
template <typename T> using min_pq = priority_queue<T, vector<T>, greater<T>>;
double solve(signed nbSommets, signed nbAretes, signed maxDiv, signed arrival,
vector<signed> x, vector<signed> y, vector<signed> cost,
vector<signed> effect) {
vector<vector<pair<int, int>>> adj(nbSommets);
for (int i = 0; i < nbAretes; ++i) {
adj[x[i]].emplace_back(y[i], cost[i]);
adj[y[i]].emplace_back(x[i], cost[i]);
}
dbg(maxDiv, arrival);
dbg(x);
dbg(y);
dbg(cost);
dbg(effect);
vector<bool> reachable(nbSommets);
reachable[0] = true;
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == arrival)
continue;
for (auto [v, c] : adj[u])
if (!reachable[v]) {
reachable[v] = true;
q.push(v);
}
}
maxDiv = min(maxDiv, 100);
vector<double> curDis(nbSommets, INF);
curDis[0] = 0;
for (int u = 0; u < nbSommets; ++u)
if (reachable[u] and effect[u] == 0)
curDis[u] = 0;
for (int iter = 0; iter <= maxDiv; ++iter) {
min_pq<pair<double, int>> pq;
for (int u = 0; u < nbSommets; ++u)
if (curDis[u] < INF)
pq.emplace(curDis[u], u);
vector<double> nxtDis(nbSommets, INF);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (u == arrival)
continue;
if (d > nxtDis[u])
continue;
for (auto [v, c] : adj[u])
if (d + c < nxtDis[v]) {
nxtDis[v] = d + c;
pq.emplace(nxtDis[v], v);
}
}
dbg(curDis);
for (int u = 0; u < nbSommets; ++u) {
curDis[u] = min(curDis[u], nxtDis[u]);
if (iter < maxDiv and effect[u] == 2 and nxtDis[u] < INF)
curDis[u] = min(curDis[u], nxtDis[u] / 2);
}
}
return curDis[arrival] == INF ? -1 : curDis[arrival];
}
