#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 90; const ll INF = 1e18;
pii adj[Nm][Nm]; //{travel time, latest leaving time}
vector<pii> dp[Nm][Nm]; //{latest leaving time, travel time}
ll dp3[Nm][Nm]; //time if leaving at start of day
ll rup(ll x, ll S) {
ll y = x/S;
if (x>(y*S)) {
return (y+1)*S;
} else {
return x;
}
}
struct hashPii {
size_t operator()(const pii &p) const { return p.first ^ (p.second>>15) ^ (p.second<<15); }
};
vector<pii> prc(vector<pii> vp0) {
unordered_set<pii,hashPii> s0;
for (pii p0: vp0) {
s0.insert(p0);
}
vector<pii> v1;
for (pii p1: s0) {
v1.push_back(p1);
}
return v1;
}
vector<ll> calculate_necessary_time(int N, int M, ll S, int Q, vector<int> A,
vector<int> B, vector<ll> L, vector<ll> C, vector<int> U, vector<int> V, vector<ll> T) {
for (ll i=0;i<Nm;i++) {
for (ll j=0;j<Nm;j++) {
adj[i][j]={INF,-INF};
}
}
vector<pair<ll,pii>> vxy;
for (ll m=0;m<M;m++) {
adj[A[m]][B[m]]={L[m],C[m]-L[m]};
adj[B[m]][A[m]]=adj[A[m]][B[m]];
vxy.push_back({C[m]-L[m],{A[m],B[m]}});
vxy.push_back({C[m]-L[m],{B[m],A[m]}});
}
sort(vxy.begin(),vxy.end());
for (auto pxy: vxy) {
ll x = pxy.second.first;
ll y = pxy.second.second;
vector<ll> dp2(N,INF);
vector<bool> pr2(N,false); //is processed
dp2[y]=adj[x][y].first+adj[x][y].second;
while (1) {
ll zc = -1; ll tc = INF;
for (ll z=0;z<N;z++) {
if (!pr2[z] && dp2[z]<tc) {
zc = z; tc = dp2[z];
}
}
if (zc == -1) {
break;
}
pr2[zc]=1;
for (ll z1=0;z1<N;z1++) {
if (tc<=adj[zc][z1].second) {
dp2[z1] = min(dp2[z1],tc+adj[zc][z1].first);
}
}
}
vector<ll> dp1(N,-INF);
vector<bool> pr1(N,false);
dp1[x]=adj[x][y].second;
while (1) {
ll zc = -1; ll tc = -INF;
for (ll z=0;z<N;z++) {
if (!pr1[z] && dp1[z]>tc) {
zc = z; tc = dp1[z];
}
}
if (zc==-1) {
break;
}
pr1[zc]=1;
for (ll z1=0;z1<N;z1++) {
if (tc<=(adj[z1][zc].first+adj[z1][zc].second) && (tc-adj[zc][z1].first)>=0LL) {
dp1[z1] = max(dp1[z1],tc-adj[zc][z1].first);
}
}
}
for (ll a=0;a<N;a++) {
for (ll b=0;b<N;b++) {
if (a!=b && dp1[a]!=-INF && dp2[b]!=INF) {
dp[a][b].push_back({dp1[a],dp2[b]-dp1[a]});
}
}
}
}
for (ll x=0;x<N;x++) {
for (ll y=0;y<N;y++) {
dp3[x][y]=INF;
if (x==y || dp[x][y].size()==0) {
continue;
}
//dp: {latest leaving time, travel time}
//dptw: {travel time, latest leaving time}
vector<pii> dptw;
for (pii p0: dp[x][y]) {
dptw.push_back({p0.second,p0.first});
}
dptw = prc(dptw);
sort(dptw.begin(),dptw.end());
dp[x][y].clear();
ll llt0 = -INF;
for (pii p0: dptw) {
if (p0.second>llt0) {
llt0 = p0.second;
dp[x][y].push_back({p0.second,p0.first});
}
}
dp3[x][y]=dptw[0].first;
}
}
for (ll k=0;k<N;k++) {
for (ll i=0;i<N;i++) {
for (ll j=0;j<N;j++) {
if (i==j) {
continue;
}
dp3[i][j]=min(dp3[i][j],rup(dp3[i][k],S)+dp3[k][j]);
}
}
}
vector<ll> ansv; //ans vector
for (ll q=0;q<Q;q++) {
ll ans = INF;
ll x = U[q]; ll y = V[q]; ll t0 = T[q];
auto A0 = lower_bound(dp[x][y].begin(),dp[x][y].end(),(pii){t0,-INF});
if (A0 != dp[x][y].end()) {
ans = (*A0).second;
}
for (ll z=0;z<N;z++) {
if (dp[x][z].size()>0 && dp[x][z].back().first>=t0) {
ans = min(ans,S-t0+dp3[z][y]);
}
}
ans = min(ans,S-t0+dp3[x][y]);
ansv.push_back(ans);
}
return ansv;
//exit(0);
}
