#include "escape_route.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 100;
const llong INF = 1e18;
const int INTINF = 1e9;
int n, m, q;
llong s;
struct Edge
{
llong w, l;
Edge()
{
w = 1;
l = 0;
}
Edge(llong _w, llong _l)
{
w = _w;
l = _l;
}
};
struct Query
{
int u, v;
llong time;
int idx;
friend bool operator < (const Query &a, const Query&b)
{
return a.u < b.u || (a.u == b.u && a.time < b.time);
}
};
Edge e[MAXN][MAXN];
std::vector <Query> queries;
std::pair <int,llong> days[MAXN][MAXN];
llong zeroTime[MAXN][MAXN];
llong queryDist[MAXN];
int dijkstraPar[MAXN];
bool vis[MAXN];
void runDijkstra(int node, llong time, llong dist[], bool shouldType)
{
// std::cout << "run dijkstra: " << node << ' ' << time << '\n';
std::priority_queue <std::pair <llong,int>> pq;
std::fill(dijkstraPar, dijkstraPar + n, -1);
std::fill(dist, dist + n, INF);
std::fill(vis, vis + n, false);
dist[node] = time;
pq.push({time, node});
while (pq.size())
{
auto [currDist, node] = pq.top();
pq.pop();
if (vis[node])
{
continue;
}
vis[node] = true;
for (int u = 0 ; u < n ; ++u)
{
if (dist[node] + e[node][u].w <= e[node][u].l && dist[u] > dist[node] + e[node][u].w)
{
dijkstraPar[u] = node;
dist[u] = dist[node] + e[node][u].w;
pq.push({-dist[u], u});
}
}
}
if (!shouldType) return;
for (int i = 0 ; i < n ; ++i)
{
if (dist[i] != INF) days[node][i] = {0, dist[i]};
else
{
days[node][i] = {INTINF, INF};
}
}
}
std::vector <llong> calculate_necessary_time(int N, int M, long long S, int Q, std::vector <int> A, std::vector <int> B, std::vector <llong> L, std::vector <llong> C, std::vector <int> U, std::vector <int> V, std::vector <llong> T)
{
// std::cout << "call\n" << std::flush;
n = N;
m = M;
s = S;
q = Q;
for (int i = 0 ; i < m ; ++i)
{
e[A[i]][B[i]] = {L[i], C[i]};
e[B[i]][A[i]] = {L[i], C[i]};
}
for (int i = 0 ; i < q ; ++i)
{
queries.push_back({U[i], V[i], T[i], i});
}
for (int i = 0 ; i < n ; ++i)
{
runDijkstra(i, 0, zeroTime[i], true);
}
for (int k = 0 ; k < n ; ++k)
{
for (int i = 0 ; i < n ; ++i)
{
for (int j = 0 ; j < n ; ++j)
{
if (i == j || i == k || j == k)
{
continue;
}
if (days[i][k].second == INF || days[k][j].second == INF)
{
continue;
}
std::pair <int,llong> currTry;
currTry.first = days[i][k].first + days[k][j].first + 1;
currTry.second = days[k][j].second;
// std::cout << "current try: " << i << ' ' << j << ' ' << k << ' ' << currTry.first << ' ' << currTry.second << ' ' << days[i][j].first << ' ' << days[i][j].second << '\n';
if (currTry.first < days[i][j].first || (currTry.first == days[i][j].first && currTry.second < days[i][j].second))
{
days[i][j] = currTry;
// if (i == 0 && j == 3) std::cout << "dist: " << i << ' ' << j << " = " << dist[i][j].first << ' ' << dist[i]
}
}
}
}
std::vector <llong> res(q);
std::sort(queries.begin(), queries.end());
int lastNode = -1;
llong toTime = 0;
llong lastT = 0;
for (int i = 0 ; i < q ; ++i)
{
// std::cout << "new query: " << i << "\n\n";
int u = queries[i].u;
int v = queries[i].v;
llong t = queries[i].time;
int idx = queries[i].idx;
if (u != lastNode || t > toTime)
{
toTime = INF;
runDijkstra(u, t, queryDist, false);
for (int i = 0 ; i < n ; ++i)
{
if (dijkstraPar[i] != -1) toTime = std::min(toTime, e[dijkstraPar[i]][i].l - e[dijkstraPar[i]][i].w - queryDist[dijkstraPar[i]] + t);
}
lastNode = u;
lastT = t;
}
if (queryDist[v] != INF)
{
res[idx] = queryDist[v] - lastT;
continue;
}
std::pair <int,llong> answer = {INTINF, INF};
for (int node = 0 ; node < n ; ++node)
{
if (queryDist[node] != INF)
{
// std::cout << "here: " << node << ' ' << v << ' ' << days[node][v].first << ' ' << days[node][v].second << '\n';
if (answer.first > days[node][v].first || (answer.first == days[node][v].first && answer.second > days[node][v].second))
{
answer = days[node][v];
}
}
}
res[idx] = 1LL * (1 + answer.first) * s + answer.second - t;
}
return res;
}
