代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define mp make_pair
#define ft first
#define sc second
#define pb push_back
#define PQ priority_queue
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define dep(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
int qreadInt() {
	int x = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') (x *= 10) += (ch - '0'), ch = getchar();
	return x;
}
long long qreadLL() {
	long long x = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') (x *= 10) += (ch - '0'), ch = getchar();
	return x;
}

//-------------------------head------------------------------

struct xint {
	int u, v, l, a;
	inline bool operator<(const xint &p)const {
		return a > p.a;
	}
}w[600010];

int fst[800010], nxt[800010], lst[800010], des[800010], dis[800010], cnt = 0;
int val[600010], vis[600010], lson[600010], rson[600010], fa[600010];
int grand[600010][21], lmt[600010], fa2[600010];
priority_queue< pii > pq;

void add(int u, int v, int w) {
	if (!fst[u]) fst[u] = ++cnt;
	else nxt[lst[u]] = ++cnt;
	des[cnt] = v, lst[u] = cnt, dis[cnt] = w;
}

int n, m;

void pre() {
	while (!pq.empty()) pq.pop();
	memset(vis, 0, sizeof vis);
	memset(val, 0x7f, sizeof val);
	pq.push(mp(0, 1)); val[1] = 0;
	while (!pq.empty()) {
		pii t = pq.top(); pq.pop();
		if (vis[t.sc]) continue;
		vis[t.sc] = 1;
		for (int i = fst[t.sc]; i; i = nxt[i])
			if (val[t.sc] + dis[i] < val[des[i]]) {
				val[des[i]] = val[t.sc] + dis[i];
				pq.push(mp(-val[des[i]], des[i]));
			}
	}
	// rep(i, 1, n) cerr << i << " " << val[i] << endl;
}

int now;
int getfa(int u) {
	if (fa2[u] != u) fa2[u] = getfa(fa2[u]);
	return fa2[u];
}

int main() {

	// freopen("return.in", "r", stdin);
	// freopen("return.out", "w", stdout);

	int T = qreadInt();
	while (T --) {
		memset(fst, 0, sizeof fst);
		memset(nxt, 0, sizeof nxt);
		// memset(des, 0, sizeof des);
		memset(lst, 0, sizeof lst);
		// memset(dis, 0, sizeof dis);
		// memset(val, 0, sizeof val);
		// memset(fa, 0, sizeof fa);
		// memset(fa2, 0, sizeof fa2);
		cnt = 0;
		// cerr << "check" << endl;
		n = qreadInt(), m = qreadInt();
		// cerr << n << " " << m << endl;
		// cerr << clock() << endl;
		rep(i, 1, m)
			w[i].u = qreadInt(), w[i].v = qreadInt(), w[i].l = qreadInt(), w[i].a = qreadInt();
		// cerr << clock() << endl;
		sort(w + 1, w + m + 1);
		rep(i, 1, m) add(w[i].u, w[i].v, w[i].l), add(w[i].v, w[i].u, w[i].l);
		// cerr << "check" << endl;
		// cerr << clock() << endl;
		pre(); now = n;
		rep(i, 1, n) fa2[i] = fa[i] = i;
		// cerr << "check" << endl;
		// cerr << clock() << endl;
		rep(i, 1, m) {
			now ++; fa2[now] = now, fa2[w[i].u] = getfa(w[i].u), fa2[w[i].v] = getfa(w[i].v);
			lson[now] = fa2[w[i].u], rson[now] = fa2[w[i].v];
			val[now] = min(val[lson[now]], val[rson[now]]);
			fa[now] = fa[fa2[w[i].u]] = fa[fa2[w[i].v]] = now;
			fa2[fa2[w[i].u]] = fa2[fa2[w[i].v]] = now;
			lmt[now] = w[i].a;
		}
		// cerr << clock() << endl;
		rep(i, 1, now) grand[i][0] = fa[i]; 
		rep(i, 1, 20) rep(j, 1, now) grand[j][i] = grand[grand[j][i - 1]][i - 1];
		int Q = qreadInt(), k = qreadInt(), s = qreadInt();
		rep(i, 1, n) lmt[i] = s + 1;
		// cerr << now << endl;
		// rep(i, 1, now) cerr << val[i] << " " << lmt[i] << " " << i << " " << fa[i] << " " << lson[i] << " " << rson[i] << endl;
		int lastans = 0;
		// cerr << clock() << endl;
		while (Q --) {
			int v0 = qreadInt(), p0 = qreadInt();
			v0 = (v0 + k * lastans - 1) % n + 1;
			p0 = (p0 + k * lastans) % (s + 1);
			int res = v0;
			dep(i, 20, 0) if (lmt[grand[res][i]] > p0) res = grand[res][i];
			// cerr << Q << " " << res << " " << v0 << " " << p0 << endl;
			lastans = val[res];
			printf("%d\n", lastans);
		}
		// cerr << clock() << endl << endl;
	}
	return 0;

}

评测结果