#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 h, vector<int> arr, priority_queue<pii> &q, vector<double> &dis, vector<bool> &vis){ if (!arr[nd]){ q.push({0, nd}); dis[nd] = 0; } vis[nd] = 1; for (auto i : E[nd]){ if (vis[i.ff] or i.ff == h) continue; dfs(i.ff, h, arr, q, dis, vis); } } 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<bool> vis(n, 0); vector<double> dis(n, 1e18); vector<int> cur(n, 0); priority_queue<pii> q; q.push({0, 0}); dis[0] = 0; dfs(0, h, arr, q, dis, vis); while(!q.empty()){ int x = q.top().ss; q.pop(); for (auto i : E[x]){ int t=0; double res = dis[x]+i.ss; if (arr[i.ff] == 2){ if (cur[x] < k){res /= 2;t=1;} } if (dis[i.ff] > res){ dis[i.ff] = res; cur[i.ff] = cur[x]+t; q.push({-dis[i.ff], i.ff}); } } } if (dis[h] == 1e18) return double(-1); return dis[h]; } // int main () // { // }