#include <bits/stdc++.h> #include "cyberland.h" using namespace std; typedef long long ll; const int N = 1e6 + 1; vector<pair<int, int>> g[N]; int f, maxn; double dijkstra(vector<int> &x) { double d[N]; for (int j = 0; j < maxn; j++) { d[j] = 1e15; } set<pair<double, int>> st; for (int j : x) { d[j] = 0; st.insert({d[j], j}); } while (!st.empty()) { int v = (*st.begin()).second; st.erase({d[v], v}); for (auto [to, w] : g[v]) { if (d[to] > d[v] + w) { st.erase({d[to], to}); d[to] = d[v] + w; st.insert({d[to], to}); } } } return d[f]; } 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) { f = h; maxn = n; for (int i = 0; i < n; i++) { g[i].clear(); } for (int i = 0; i < m; i++) { g[x[i]].push_back({y[i], c[i]}); g[y[i]].push_back({x[i], c[i]}); } queue<int> q; vector<int> can(n,0); can[0] = 1; q.push(0); while(!q.empty()){ int v = q.front(); q.pop(); for(auto [to,w]:g[v]){ if(to == h || can[to]) continue; q.push(to); can[to] = 1; } } vector<int> vv(1, 0); double res = dijkstra(vv); if (res == 1e15) return -1; vv.clear(); for (int j = 0; j < n; j++) { if (!arr[j] && can[j]) { vv.push_back(j); } } res = min(res,dijkstra(vv)); return res; } // 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)); // } // }