#include "cyberland.h"
#include <cstdlib>
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 100000, K = 120;
const double INF = 1e18;
int *ej[N], *ew[N], eo[N];
void append(int i, int j, int w) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0) {
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
}
ej[i][o] = j, ew[i][o] = w;
}
double dd[N], dd_[N]; int iq[N + 1], pq[N], cnt;
int lt(int i, int j) { return dd[i] < dd[j]; }
int p2(int p) {
return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add_last(int i) {
iq[pq[i] = ++cnt] = i;
}
int pq_remove_first() {
int i = iq[1], j = iq[cnt--];
if (j != i)
pq[j] = 1, pq_dn(j);
pq[i] = 0;
return i;
}
void dijkstra(int n) {
for (int i = 0; i < n; i++)
pq_add_last(i);
for (int h = cnt / 2; h > 0; h--)
pq_dn(iq[h]);
while (cnt) {
int i = pq_remove_first();
for (int o = eo[i]; o--; ) {
int j = ej[i][o], w = ew[i][o];
double d = dd[i] + w;
if (dd[j] > d)
dd[j] = d, pq_up(j);
}
}
}
double solve(int n, int m, int k, int t, vi ii, vi jj, vi ww, vi type) {
type[0] = 0;
for (int i = 0; i < n; i++) {
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
ew[i] = (int *) malloc(2 * sizeof *ew[i]);
eo[i] = 0;
}
for (int h = 0; h < m; h++) {
int i = ii[h], j = jj[h], w = ww[h];
if (i != t)
append(i, j, w);
if (j != t)
append(j, i, w);
}
for (int i = 0; i < n; i++)
dd[i] = INF;
dd[0] = 0;
dijkstra(n);
for (int i = 0; i < n; i++)
dd[i] = type[i] == 0 && dd[i] != INF ? 0 : INF;
dijkstra(n);
k = min(k, K);
while (k--) {
for (int i = 0; i < n; i++)
dd_[i] = dd[i];
for (int i = 0; i < n; i++)
if (type[i] == 2)
dd[i] = INF;
for (int i = 0; i < n; i++)
if (type[i] == 2 && dd_[i] != INF)
for (int o = eo[i]; o--; ) {
int j = ej[i][o], w = ew[i][o];
dd[j] = min(dd[j], dd_[i] / 2 + w);
}
dijkstra(n);
}
return dd[t] == INF ? -1 : dd[t];
}
