#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <functional> using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; //set.find_by_order(x) x-position value //set.order_of_key(x) number of strictly less elements don't need *set.?? #define N 100005 #define wr cout << "Continue debugging\n"; #define all(x) (x).begin(), (x).end() #define ll long long int #define pii pair <int, int> #define pb push_back #define ff first #define ss second vector<pii> E[N]; void dfs(int nd, int pr, int h, vector<int> arr, priority_queue<pii> &q, vector<ll> &dis){ if (!arr[nd]){ q.push({0, nd}); dis[nd] = 0; } for (auto i : E[nd]){ if (i.ff == pr or i.ff == h) continue; dfs(i.ff,nd,h,arr,q,dis); } } double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){ for (int i = 0; i < n; i++) E[i].clear(); for (int i = 0; i < m; i++){ E[x[i]].pb({y[i], c[i]}); E[y[i]].pb({x[i], c[i]}); } vector<ll> dis(n, 1e18); priority_queue<pii> q; q.push({0, 0}); dis[0] = 0; dfs(0, -1, h, arr, q, dis); while(!q.empty()){ int x = q.top().ss; q.pop(); for (auto i : E[x]){ if (dis[i.ff] > dis[x]+i.ss){ dis[i.ff] = dis[x]+i.ss; q.push({i.ss, i.ff}); } } } return double(dis[h]); } // int main () // { // }