#include "cyberland.h" #include<bits/stdc++.h> using namespace std; #define ll long long int #define pb push_back #define all(x) x.begin(), x.end() const int SZ = 2e5; int _H; double po[95]; vector<pair<int, double>> g[SZ]; vector<bool> VIS; void dfs(int v, int p){ VIS[v] = 1; for(auto U: g[v]){ int u = U.first; if(!VIS[u] && u != _H) dfs(u, v); } } 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(int i = 0; i < N; ++i) g[i].clear(); _H = H; VIS.clear(); VIS.resize(N); K = min(K, 90); po[0] = 1; for(int i = 1; i < 95; ++i) po[i] = po[i - 1] * 2; vector<vector<double>> dist(N); vector<vector<bool>> vis(N); for(int i = 0; i < M; ++i) g[x[i]].pb({y[i], c[i]}), g[y[i]].pb({x[i], c[i]}); for(int i = 0; i < N; ++i) dist[i].resize(K + 1, -1), vis[i].resize(K + 1); dist[H][0] = 0; set<array<double, 3>> Q; Q.insert({0, H, 0}); while(!Q.empty()){ auto it = *Q.begin(); int v = it[1], k = it[2]; Q.erase(Q.begin()); if(vis[v][k]) continue; vis[v][k] = 1; for(auto U: g[v]){ int u = U.first; if(u == H) continue; double w = U.second; if(arr[v] == 2 && k + 1 <= K && (dist[u][k + 1] == -1 || dist[u][k + 1] > dist[v][k] + w / po[k + 1])){ Q.erase({dist[u][k + 1], u, k + 1}); dist[u][k + 1] = dist[v][k] + w / po[k + 1]; Q.insert({dist[u][k + 1], u, k + 1}); } if(dist[u][k] == -1 || dist[u][k] > dist[v][k] + w / po[k]){ Q.erase({dist[u][k], u, k}); dist[u][k] = dist[v][k] + w / po[k]; Q.insert({dist[u][k], u, k}); } } } if(!vis[0][0]) return -1; double ans = -1; dfs(0, 0); for(int i = 0; i < N; ++i){ if(VIS[i] && (arr[i] == 0 || i == 0)){ for(int j = 0; j <= K; ++j){ if(dist[i][j] == -1) continue; ans = ans == -1 || ans > dist[i][j] ? dist[i][j] : ans; } } } return ans; }

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:45:16: warning: narrowing conversion of 'H' from 'int' to 'double' [-Wnarrowing]
   45 |   Q.insert({0, H, 0});
      |                ^
cyberland.cpp:58:32: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   58 |       Q.erase({dist[u][k + 1], u, k + 1});
      |                                ^
cyberland.cpp:58:37: warning: narrowing conversion of '(k + 1)' from 'int' to 'double' [-Wnarrowing]
   58 |       Q.erase({dist[u][k + 1], u, k + 1});
      |                                   ~~^~~
cyberland.cpp:60:34: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   60 |        Q.insert({dist[u][k + 1], u, k + 1});
      |                                  ^
cyberland.cpp:60:39: warning: narrowing conversion of '(k + 1)' from 'int' to 'double' [-Wnarrowing]
   60 |        Q.insert({dist[u][k + 1], u, k + 1});
      |                                     ~~^~~
cyberland.cpp:63:29: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   63 |        Q.erase({dist[u][k], u, k});
      |                             ^
cyberland.cpp:63:32: warning: narrowing conversion of 'k' from 'int' to 'double' [-Wnarrowing]
   63 |        Q.erase({dist[u][k], u, k});
      |                                ^
cyberland.cpp:65:30: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   65 |        Q.insert({dist[u][k], u, k});
      |                              ^
cyberland.cpp:65:33: warning: narrowing conversion of 'k' from 'int' to 'double' [-Wnarrowing]
   65 |        Q.insert({dist[u][k], u, k});
      |                                 ^