#include "escape_route.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; std::vector<long long> calculate_necessary_time( int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B, std::vector<long long> L, std::vector<long long> C, std::vector<int> U, std::vector<int> V, std::vector<long long> T) { vector<ll> ans(Q); vector<vector<ll>> queries(N); for(int i=0; i<Q; ++i) { queries[U[i]].push_back(i); } vector<vector<pair<int, int>>> g(N); for(int i=0; i<M; ++i) { g[A[i]].push_back({B[i], i}); g[B[i]].push_back({A[i], i}); } ll inf = 1e18; for(int s=0; s<N; ++s) { for(auto idx : queries[s]) { vector<ll> dist(N, inf), vis(N,0); dist[s] = T[idx]; while(1) { pair<ll, ll> best = {inf,0}; for(int i=0; i<N; ++i) if(!vis[i]) best = min(best, {dist[i], i}); if(best.first == inf) break; auto[dv,v] = best; vis[v] = 1; for(auto[u,k] : g[v]) { ll w = L[k]; if(dv > C[k] - L[k]) w += S-dv; if(dist[u] > dist[v] + w) { dist[u] = dist[v] + w; } } } ans[idx] = dist[V[idx]]; } } return ans; }