~~被拖去晚自习了，所以十点前楼主都死了（~~
by Karl_Aurora @ 2022-11-02 18:18:36
dfs 卡死是因为没有手动开栈，TLE 估计是询问时写挂了，dfs 不会 T
by Gmt丶future @ 2022-11-02 18:20:32
@[Karl_Aurora](/user/260061) 将倍增时范围扩大到 Krunut，然后询问时把 while 变成 if 就行了
by Gmt丶FFF @ 2022-11-02 18:35:48
改好的（改的加了注释）
```cpp
#include <bits/stdc++.h>
#define maxn 400010
#define maxm 800010
#define maxjump 20
#define writeln(X) write(X), putchar('\n')
using namespace std;
template < typename T >
inline void read(T &X)
{
X = 0; bool f = false; char ch = getchar();
while (!isdigit(ch)) {f |= ch == '-'; ch = getchar();}
while (isdigit(ch)) {X = (X * 10) + (ch ^ 48); ch = getchar();}
X = f ? -X : X;
}
template < typename T >
inline void write(T X)
{
if (X == 0) {putchar('0'); return;}
if (X < 0) {putchar('-'); X = -X;}
static int num[21], cnt = 0;
while (X) {num[++cnt] = X % 10; X /= 10;}
while (cnt) putchar(num[cnt--] ^ 48);
}
struct disside {int v, w, next;} dissidelist[maxm << 1];
int dissidecnt, head[maxn];
inline void buildside(const int &u, const int &v, const int &w) {dissidelist[++dissidecnt] = {v, w, head[u]}; head[u] = dissidecnt;}
int n, m;
struct heapnode
{
int id, val;
heapnode (const int &_id = 0, const int &_val = 0) : id(_id), val(_val) {}
bool operator < (const heapnode &b) const {return this->val > b.val;}
};
int dis[maxn];
priority_queue < heapnode > q;
//关于SPFA,它死了
inline void dijk()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0; q.emplace(1, 0);
while(!q.empty())
{
int x = q.top().id, w = q.top().val;
q.pop();
if (w > dis[x]) continue;
for (int i = head[x]; i; i = dissidelist[i].next)
{
int to = dissidelist[i].v, d = dis[x] + dissidelist[i].w;
if (d < dis[to]) q.emplace(to, d), dis[to] = d;
}
}
}
struct side
{
int u, v, w;
bool operator < (const side &b) const {return this->w > b.w;}
}sidelist[maxm];
int fa[maxn << 1], val[maxn << 1];
int Krucnt;
int getfa(const int &x)
{
if (fa[x] == x) return x;
return fa[x] = getfa(fa[x]);
}
vector < int > Kruside[maxn];
void Kru()
{
Krucnt = n;
for (int i = 1; i <= (n << 1) - 1; ++i) fa[i] = i, Kruside[i].clear();
sort(sidelist + 1, sidelist + m + 1);
for (int i = 1; i <= m; ++i)
{
int u = sidelist[i].u, v = sidelist[i].v, w = sidelist[i].w;
u = getfa(u), v = getfa(v);
if (u != v)
{
++Krucnt;
fa[u] = Krucnt, fa[v] = Krucnt;
val[Krucnt] = w;
Kruside[Krucnt].emplace_back(u); Kruside[Krucnt].emplace_back(v);
}
if (Krucnt == (n << 1) - 1) break;
}
}
int mindis[maxn << 1];
int ST[maxn << 1][maxjump + 5];
void dfs(const int &x)
{
if (x <= n) {mindis[x] = dis[x]; return;}
mindis[x] = 0x3f3f3f3f;
for (int to : Kruside[x])
{
dfs(to);
mindis[x] = min(mindis[x], mindis[to]);
ST[to][0] = x;
}
}
int main()
{
int T;
read(T);
while (T--)
{
dissidecnt = 0; memset(head, 0, sizeof(head));
read(n); read(m);
for (int i = 1; i <= m; ++i)
{
int u, v, l, a;
read(u); read(v); read(l); read(a);
buildside(u, v, l); buildside(v, u, l);
sidelist[i] = {u, v, a};
}
dijk();
// for (int i = 1; i <= n; ++i) cerr << dis[i] << endl;
Kru();
dfs(Krucnt);
ST[Krucnt][0] = Krucnt;
for (int j = 1; j <= maxjump; ++j)
for (int i = 1; i <= Krucnt; ++i)//这里
ST[i][j] = ST[ST[i][j - 1]][j - 1];
int q, k, s, lastans = 0;
read(q); read(k); read(s);
for (int i = 1; i <= q; ++i)
{
int v, p;
read(v); read(p);
v = ((v + k * lastans - 1) % n) + 1, p = (p + k * lastans) % (s + 1);
for (int j = maxjump; j >= 0; --j)
if (val[ST[v][j]] > p ) v = ST[v][j];//这里
lastans = mindis[v];
writeln(lastans);
}
}
}
```
@[Karl_Aurora](/user/260061)
by Gmt丶FFF @ 2022-11-02 18:37:10
@[Gmt丶future](/user/461891) @[Gmt丶future](/user/461891) 谢谢！
by Karl_Aurora @ 2022-11-02 22:08:08