//#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
struct Arista
{
int v, p;
};
struct Nodo
{
vector <Arista> ady;
int ability;
int idx;
int cost0, costP = 0;
};
vector <Nodo> g;
vector <Arista> padre;
vector <bool> vis;
int h;
void clean(int N)
{
g.clear();
padre.clear();
vis.clear();
g.resize(N);
padre.resize(N);
vis.resize(N, false);
}
void dfs(int nodo)
{
if (nodo == h)
{
return;
}
for (auto i : g[nodo].ady)
{
if (!vis[i.v])
{
padre[i.v] = {nodo, i.p};
//cout<<"padre "<<i.v<<": "<<nodo<<" c: "<<i.p<<endl;
vis[i.v] = true;
dfs(i.v);
}
}
}
struct Estado
{
int p;
int idx;
};
struct Comp
{
bool operator() (Estado a, Estado b) const
{
return a.p > b.p;
}
};
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)
{
h = H;
clean(N);
for (int i = 0; i < M; i++)
{
g[x[i]].ady.push_back({y[i], c[i]});
g[y[i]].ady.push_back({x[i], c[i]});
}
for (int i = 0; i < N; i++)
{
g[i].ability = arr[i];
g[i].idx = i;
}
///////////dijkstra desde los 0's
priority_queue <Estado, vector <Estado>, Comp> pq;
vector <bool> assigned(N, false);
for (auto i : g)
{
if (i.ability == 0)
{
assigned[i.idx] = true;
pq.push({0, i.idx});
g[i.idx].cost0 = 0;
}
}
while (!pq.empty())
{
Estado curr = pq.top();
pq.pop();
if (!assigned[curr.idx])
{
g[curr.idx].cost0 = g[curr.idx].costP;
assigned[curr.idx] = true;
for (auto i : g[curr.idx].ady)
{
g[i.v].costP = min(g[i.v].costP, curr.p+ i.p);
pq.push({g[i.v].costP, i.v});
}
}
}
////////////
vis[0] = true;
padre[0] = {-1, 0};
dfs(0);
int curr = H;
vector <Arista> camino(N);
while (curr != -1)
{
camino[padre[curr].v].v = curr;
camino[padre[curr].v].p = padre[curr].p;
curr =(double) padre[curr].v;
}
double cost = 0;
curr = 0;
while (curr != h)
{
cost = min(cost, (double) g[curr].cost0);
cost += (double)camino[curr].p;
curr = camino[curr].v;
}
return (double)cost;
}
