#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
const ll N=100005;
vector< pair< ll, ll > > v[N];
double T[N][32];
bool B[N];
ll Ra[N];
void DFS(ll s, ll f){
Ra[s]=1;
if(s==f) return;
ll vn=v[s].size();
for(int i=0; i<vn; i++){
if(!B[v[s][i].ff]){
B[v[s][i].ff]=true;
DFS(v[s][i].ff, f);
}
}
return;
}
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){
for(ll i=0; i<N; i++){
Ra[i]=0;
B[i]=false;
v[i].clear();
}
for(ll i=0; i<M; i++){
ll X=x[i], Y=y[i], Z=c[i];
v[X].pb(mp(Y, Z));
v[Y].pb(mp(X, Z));
}
Ra[0]=1;
B[0]=true;
DFS(0, H);
if(!Ra[H]) return -1;
priority_queue< pair< double, pair< ll, ll > >, vector< pair< double, pair< ll, ll > > >, greater< pair< double, pair< ll, ll > > > > q;
for(ll i=0; i<N; i++){
if(Ra[i] && !arr[i]){
q.push(mp(0.0, mp(0, i)));
for(ll j=0; j<=30; j++){
T[i][j]=0.0;
}
}
else if(i==0){
q.push(mp(0.0, mp(0, i)));
for(ll j=0; j<=30; j++){
T[i][j]=0.0;
}
}
else{
for(ll j=0; j<=30; j++){
T[i][j]=1000000000000000000.0;
}
}
}
while(!q.empty()){
double fx=q.top().ff;
ll fy=q.top().ss.ff;
ll fz=q.top().ss.ss;
q.pop();
if(T[fz][fy]<fx){
continue;
}
if(fz==H){
continue;
}
ll vn=v[fz].size();
for(ll i=0; i<vn; i++){
double dd=v[fz][i].ss*1.0;
double fare=fx+dd;
if(arr[v[fz][i].ff]==1){
if(fare<T[v[fz][i].ff][fy]){
q.push(mp(fare, mp(fy, v[fz][i].ff)));
T[v[fz][i].ff][fy]=fare;
}
}
if(arr[v[fz][i].ff]==2){
if(fare<T[v[fz][i].ff][fy]){
q.push(mp(fare, mp(fy, v[fz][i].ff)));
T[v[fz][i].ff][fy]=fare;
}
if(fy+1<=K && fare/2.0<T[v[fz][i].ff][fy+1]){
fare/=2.0;
q.push(mp(fare, mp(fy+1, v[fz][i].ff)));
T[v[fz][i].ff][fy+1]=fare;
}
}
}
}
double ans=1000000000000000000.0;
for(ll i=0; i<=K; i++){
ans=min(ans, T[H][i]);
}
return ans;
}
int main() {
int T;
assert(1 == scanf("%d", &T));
while (T--){
int N,M,K,H;
assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
std::vector<int> x(M);
std::vector<int> y(M);
std::vector<int> c(M);
std::vector<int> arr(N);
for (int i=0;i<N;i++)
assert(1 == scanf("%d", &arr[i]));
for (int i=0;i<M;i++)
assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
}
}
Compilation message
/usr/bin/ld: /tmp/ccmIyYGV.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCGB7pS.o:cyberland.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
