代码

#include <cstdio>
#include <algorithm>
#include <queue>

namespace fastio
{
	const int MAXBUF = 1 << 23;
	char buf[MAXBUF], *p1 = buf, *p2 = buf;
	char pbuf[MAXBUF], *pp = pbuf;
	inline char getc() { return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, MAXBUF, stdin)), p1 == p2 ? EOF : *p1++; }
	inline void putc(char c) { (pp == pbuf + MAXBUF) && (fwrite(pbuf, 1, MAXBUF, stdout), pp = pbuf), *pp++ = c; }
	inline void print_final() { fwrite(pbuf, 1, pp - pbuf, stdout), pp = pbuf; }
}
using fastio::getc;
using fastio::putc;
using fastio::print_final;
template <class _Tp>
inline _Tp& read(_Tp& x)
{
	bool sign = 0;
	char ch = getc();
	for (; !('0' <= ch && ch <= '9'); ch = getc()) sign |= (ch == '-');
	for (x = 0; '0' <= ch && ch <= '9'; ch = getc()) x = x * 10 + (ch ^ 48);
	return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x)
{
	if (x < 0) putc('-'), x = -x;
	if (x > 9) write(x / 10);
	putc((x % 10) ^ 48);
}

const int maxn = 2e5 + 10, maxm = 4e5 + 10;

struct graph
{
	int cnt = 0, st[maxm * 2], to[maxm * 2], w[maxm * 2], next[maxm * 2], last[maxn];
	void init(int n) { cnt = 0; for (int i = 1; i <= n; i++) last[i] = 0; }
	void add(int x, int y, int z) { cnt++, st[cnt] = x, to[cnt] = y, w[cnt] = z, next[cnt] = last[x], last[x] = cnt; }
}
g;

struct edge
{
	int u, v, h;
	bool operator < (const edge &t) const { return h > t.h; }
}
e[maxm];

bool mark[maxn];
int dis[maxn];

struct dsu
{
	int fa[maxn * 2];
	void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; }
	int getfa(int u) { return fa[u] == u ? u : fa[u] = getfa(fa[u]); }
}
d;

int f[2 * maxn][std::__lg(2 * maxn) + 5];
int ls[2 * maxn], rs[2 * maxn];
int h[2 * maxn];

int find(int u, int x, int K)
{
	for (int j = K; j >= 0; j--) if (h[f[u][j]] > x) u = f[u][j];
	return u;
}

int min[2 * maxn];

int dfs(int u)
{
	if (ls[u] == 0 && rs[u] == 0) return min[u] = dis[u];
	else return min[u] = std::min(dfs(ls[u]), dfs(rs[u]));
}

int main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	int T;
	read(T);
	while (T--)
	{
		int n, m;
		read(n), read(m);
		g.init(n);
		for (int i = 1; i <= m; i++)
		{
			int u, v, w, h;
			read(u), read(v), read(w), read(h);
			e[i] = edge{u, v, h}, g.add(u, v, w), g.add(v, u, w);
		}
		for (int i = 1; i <= n; i++) dis[i] = 2e9, mark[i] = 0;
		dis[1] = 0;
		std::priority_queue<std::pair<int, int>> que;
		que.push({0, 1});
		while (!que.empty())
		{
			int u = que.top().second;
			que.pop();
			if (mark[u]) continue;
			mark[u] = 1;
			for (int j = g.last[u]; j != 0; j = g.next[j])
			{
				int v = g.to[j];
				if (dis[v] > dis[u] + g.w[j])
				{
					dis[v] = dis[u] + g.w[j];
					que.push({-dis[v], v});
				}
			}
		}
		std::sort(e + 1, e + m + 1);
		d.init(2 * n);
		int tot = n;
		h[0] = -2e9;
		for (int i = 1; i <= n; i++) h[i] = 2e9, ls[i] = rs[i] = 0;
		for (int i = 1; i <= m; i++)
		{
			int u = e[i].u, v = e[i].v;
			u = d.getfa(u), v = d.getfa(v);
			if (u == v) continue;
			tot++;
			f[u][0] = f[v][0] = d.fa[u] = d.fa[v] = tot;
			f[tot][0] = 0, ls[tot] = u, rs[tot] = v, h[tot] = e[i].h;
		}
		int K = std::__lg(tot) + 1;
		for (int j = 1; j <= K; j++) for (int i = 1; i <= tot; i++) f[i][j] = f[f[i][j - 1]][j - 1];
		dfs(tot);
		int q, t, s;
		read(q), read(t), read(s);
		int lastans = 0;
		while (q--)
		{
			int u, p;
			read(u), read(p);
			u = (u + t * lastans - 1) % n + 1;
			p = (p + t * lastans) % (s + 1);
			int v = find(u, p, K);
			lastans = min[v];
			write(lastans), putc('\n');
		}
	}
	return print_final(), 0;
}

评测结果