#include "escape_route.h"
#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define MOD (int)(1000000007)
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 100;
const int MAXQ = 3000030;
const int INF = 8e18;
struct Edge {
int c, l; // close time, length
};
struct Query {
int u, v, t, id;
};
struct Path {
int s, t, d, l;
bool operator<(const Path &p) const {
return l < p.l;
}
};
int N, M, S, Q;
Edge adj[MAXN][MAXN];
pii owo[MAXN][MAXN];
int vis[MAXN];
int dist[MAXN][MAXN];
int rem[MAXN][MAXN];
bool ok[MAXN][MAXN];
vector<Query> qry;
vector<int> ans;
// starting from time=0
void meow(int s) {
For(i, 0, N - 1) {
owo[s][i] = pii(INF, INF);
vis[i] = 0;
}
owo[s][s] = pii(0, 0);
For(_, 0, N - 1) {
int idx = -1;
pii mn(INF, INF);
For(i, 0, N - 1) if(!vis[i]) {
if(owo[s][i] < mn) {
mn = owo[s][i];
idx = i;
}
}
assert(idx >= 0);
vis[idx] = 1;
For(i, 0, N - 1) if(adj[idx][i].l > 0) {
pii nt(mn.first, mn.second + adj[idx][i].l);
if(nt.second > adj[idx][i].c) {
nt = pii(mn.first + 1, adj[idx][i].l);
}
owo[s][i] = min(owo[s][i], nt);
}
}
}
int nya() {
int u, v, t;
u = qry.back().u; v = qry.back().v; t = qry.back().t;
int pos = qry.back().id;
qry.pop_back();
// cout << "========\n";
// For(j, 0, N - 1) For(i, 0, N - 1) {
// if(dist[j][i] >= INF) cout << "-1";
// else cout << dist[j][i];
// cout << " \n"[i == N - 1];
// }
// cout << "========\n";
if(dist[u][v] != INF) return ans[pos] = dist[u][v];
int res = INF;
For(i, 0, N - 1) if(dist[u][i] != INF) {
auto tm = owo[i][v];
res = min(res, S * (tm.first + 1) + tm.second - t);
}
// cout << "-> " << u << " " << v << " " << t << " " << pos << "\n";
return ans[pos] = res;
}
std::vector<long long> calculate_necessary_time(
int32_t _N, int32_t _M, long long _S, int32_t _Q, std::vector<int32_t> A, std::vector<int32_t> B,
std::vector<long long> L, std::vector<long long> C, std::vector<int32_t> U,
std::vector<int32_t> V, std::vector<long long> T) {
N = _N; M = _M; S = _S; Q = _Q;
For(i, 0, N - 1) For(j, 0, N - 1) {
adj[i][j] = {-1, -1};
dist[i][j] = (i == j ? 0 : INF);
rem[i][j] = (i == j ? INF : -INF);
ok[i][j] = 0;
}
priority_queue<Path> pq;
For(i, 0, M - 1) {
int a = A[i];
int b = B[i];
int l = L[i];
int c = C[i];
adj[a][b] = adj[b][a] = {c, l};
pq.emplace((Path){a, b, l, c - l});
pq.emplace((Path){b, a, l, c - l});
}
For(i, 0, N - 1) meow(i);
For(i, 0, Q - 1) {
qry.eb((Query){U[i], V[i], T[i], i});
}
ans.resize(Q);
sort(all(qry), [&](auto &a, auto &b) {
return a.t < b.t;
});
while(!pq.empty()) {
Path p = pq.top(); pq.pop();
// cout << p.s << " " << p.t << " " << p.d << " " << p.l << "\n";
// expired queries
while(sz(qry) && qry.back().t > p.l) {
nya();
}
if(p.d < dist[p.s][p.t]) {
dist[p.s][p.t] = p.d;
rem[p.s][p.t] = p.l;
}
// relax
For(i, 0, N - 1) if(dist[p.t][i] < INF) {
int nd = p.d + dist[p.t][i];
int nr = min(p.l, rem[p.t][i] - p.d);
if(nr >= p.l) {
if(nd < dist[p.s][i]) {
dist[p.s][i] = nd;
rem[p.s][i] = nr;
}
} else if(nr >= 0 && nd < dist[p.s][i]) {
pq.emplace((Path){p.s, i, nd, nr});
}
}
For(i, 0, N - 1) if(dist[i][p.s] < INF) {
int nd = p.d + dist[i][p.s];
int nr = min(rem[i][p.s], p.l - dist[i][p.s]);
if(nr >= 0 && nd < dist[i][p.t]) {
pq.emplace((Path){i, p.t, nd, nr});
}
}
}
while(sz(qry)) nya();
return ans;
}
/*
g++ -std=c++14 -O2 -fsigned-char -o grader grader.cpp escape_route.cpp & grader.exe < input.txt > output.txt 2> error.txt
*/
