代码

#include <cstdio>
#include <cstring>

#include <algorithm>
#include <functional>
#include <queue>

#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

struct Node {
	int u, v, w;
	
	bool operator>(const Node& rhs) const { return w > rhs.w; }
};

struct Nde {
	int u, step;
	
	Nde() {}
	
	Nde(int u, int step) : u(u), step(step) {}
	
	bool operator>(const Nde& rhs) const { return step > rhs.step; }
};

struct Edge {
	int v, w;
	Edge* next;
};

struct Atm {
	int prt, rk, myn;
	
	Atm() {}
	
	Atm(int prt, int rk, int myn) : prt(prt), rk(rk), myn(myn) {}
};

struct Seg {
	int l, r;
	Atm v;
	Seg *ls, *rs;
	
	Atm qry(int k) const {
		if (l == r)
			return v;
		if (k <= ls->r)
			return ls->qry(k);
		return rs->qry(k);
	}
	
	void ch(int l, const Atm& v);
	
	void ord() {
		if (l == r) {
			LOG("{%d, %d, %d} ", v.prt, v.rk, v.myn);
			return;
		}
		ls->ord();
		rs->ord();
	}
};

const int N = 200010, M = 400010, LGN = 18;

int n, m;

int pri[N], dis[N];
Node ed[M];
Edge epool[M * 2];
Edge* eptop;
Edge* g[N];
Seg spool[N * LGN * 4];
Seg* sptop;
Seg* t[N];

void adde(int u, int v, int w);
void solve();
Seg* build(int l, int r);
Seg* create(int l, int r);
Seg* clone(Seg* p);
Atm find(Seg* t, int x);

int main() {
	int t;
	scanf("%d", &t);
	while (t--)
		solve();
	return 0;
}

Seg* create(int l, int r) {
	sptop->l = l;
	sptop->r = r;
	return sptop++;
}

Seg* build(int l, int r) {
	Seg* p = create(l, r);
	if (l == r) {
		p->v = Atm(l, 0, dis[l]);
		return p;
	}
	int mid = (l + r) / 2;
	p->ls = build(l, mid);
	p->rs = build(mid + 1, r);
	return p;
}

void solve() {
	scanf("%d%d", &n, &m);
	eptop = epool;
	sptop = spool;
	memset(g, 0, sizeof(g));
	
	for (int i = 1; i <= m; ++i) {
		int u, v, l, a;
		scanf("%d%d%d%d", &u, &v, &l, &a);
		adde(u, v, l);
		adde(v, u, l);
		ed[i].u = u;
		ed[i].v = v;
		ed[i].w = a;
	}
	sort(ed + 1, ed + m + 1, greater<Node>());
	
	{
		memset(dis, -1, sizeof(dis));
		priority_queue<Nde, vector<Nde>, greater<Nde> > q;
		q.push(Nde(1, dis[1] = 0));
		while (!q.empty()) {
			Nde tmp = q.top();
			q.pop();
			if (dis[tmp.u] != tmp.step)
				continue;
			for (Edge* p = g[tmp.u]; p; p = p->next)
				if (dis[p->v] == -1 || dis[p->v] > tmp.step + p->w)
					q.push(Nde(p->v, dis[p->v] = tmp.step + p->w));
		}
	}
	
	t[n] = build(1, n);
	int cnt = n;
	pri[n] = 1 << 30;
	for (int i = 1; i <= m; ++i) {
		Atm ua = find(t[cnt], ed[i].u),
		    va = find(t[cnt], ed[i].v);
		if (ua.prt == va.prt)
			continue;
		pri[cnt - 1] = ed[i].w;
		if (ua.rk < va.rk)
			swap(ua, va);
		Atm res = Atm(ua.prt, ua.rk, min(ua.myn, va.myn));
		if (ua.rk == va.rk)
			++res.rk;
		t[cnt - 1] = clone(t[cnt]);
		--cnt;
		t[cnt]->ch(ua.prt, res);
		t[cnt]->ch(va.prt, res);
	}
	
	int q, k, s;
	int lans = 0;
	scanf("%d%d%d", &q, &k, &s);
	while (q--) {
		int v, p;
		scanf("%d%d", &v, &p);
		v = (v + k * lans - 1) % n + 1;
		p = (p + k * lans) % (s + 1);
		int ind = upper_bound(pri + 1, pri + n, p) - pri;
		Atm tmp = find(t[ind], v);
		lans = tmp.myn;
		printf("%d\n", lans);
	}
}

Seg* clone(Seg* p) {
	Seg* ret = create(p->l, p->r);
	ret->ls = p->ls;
	ret->rs = p->rs;
	return ret;
}

void Seg::ch(int k, const Atm& v) {
	if (l == r) {
		this->v = v;
		return;
	}
	if (k <= ls->r) {
		ls = clone(ls);
		return ls->ch(k, v);
	}
	rs = clone(rs);
	return rs->ch(k, v);
}

Atm find(Seg* t, int x) {
	Atm ret = t->qry(x);
	while (ret.prt != x) {
		x = ret.prt;
		ret = t->qry(x);
	}
	return ret;
}

void adde(int u, int v, int w) {
	Edge* p = eptop;
	++eptop;
	p->v = v;
	p->w = w;
	p->next = g[u];
	g[u] = p;
}

评测结果