代码

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define for_v(v) for (vector<int>::iterator i=v.begin(); i!=v.end(); i++)
const int N = 200032, M = 800032;
using namespace std;

int d[N], h[N], nx[M], to[M], w[M], e;
inline void adde(int u, int v, int _w) {
	to[e] = v; w[e] = _w;
	nx[e] = h[u]; h[u] = e++;
}

struct Node {
	int d, i;
	bool operator < (Node b) const {return d > b.d;}
};
priority_queue<Node> q;
inline void upd(int i, int w) {
	if (d[i] > w) q.push((Node){d[i] = w, i});
}
void dijkstra() {
	memset(d, 0x7f, sizeof d);
	q.push((Node){d[1] = 0, 1});
	while (!q.empty()) {
		Node x = q.top(); q.pop();
		if (x.d > d[x.i]) continue;
		for (int i = h[x.i]; i; i = nx[i])
			upd(to[i], x.d + w[i]);
	}
}

struct sort_t {
	int a, i;
	bool operator < (sort_t s) const {return a > s.a;}
} seq[M>>1];

int f[N], fa[N], A[N], B[N], D[N];
vector<int> ch[N];

int find(int x) {return f[x] ? f[x] = find(f[x]) : x;}
inline void link(int i, int a) {
	int x = find(to[i]), y = find(to[i^1]);
	if (x != y) {
		if (d[x] < d[y] || x == 1) swap(x,y);
		f[x] = fa[x] = y; A[x] = a;
		ch[y].push_back(x);
	}
}

int son[N], in[N], top[N], tim;

int dfs1(int x) {
	int sz = 1, mx = 0;
	for_v (ch[x]) {
		int s = dfs1(*i);
		sz += s;
		if (s > mx) mx = s, son[x] = *i;
	}
	return sz;
}

void dfs2(int x, int tp) {
	top[x] = tp;
	in[x] = ++tim;
	B[tim] = A[son[x]];
	D[tim] = d[x];
	if (son[x]) {
		dfs2(son[x], tp);
		for_v (ch[x])
			if (*i != son[x])
				dfs2(*i, *i);
	}
}

int Query(int x, int a) {
	int tp = top[x];
	while (A[tp] > a) tp = top[x = fa[tp]];
	return D[upper_bound(B+in[tp], B+in[x], a) - B];
}

int main() {
	int T, n, m, u, v, l, a, k, S, ans = 0;
	scanf("%d",&T);
	while (T--) {
		scanf("%d%d",&n,&m);
		e = 2; tim = 0;
		memset(h, 0, sizeof h);
		memset(f, 0, sizeof f);
		memset(son, 0, sizeof son);
		for (int i = 1; i <= n; i++)
			ch[i].clear();
		sort_t *p = seq;
		while (m--) {
			scanf("%d%d%d%d",&u,&v,&l,&a);
			*p++ = (sort_t){a, e};
			adde(u,v,l); adde(v,u,l);
		}
		dijkstra();
		sort(seq, p);
		for (sort_t *i = seq; i < p; i++)
			link(i->i, i->a);
		dfs1(1);
		dfs2(1, 1);
		scanf("%d%d%d",&m,&k,&S); S++;
		while (m--) {
			scanf("%d%d",&v,&a);
			v = (v + k * ans - 1) % n + 1;
			a = (a + k * ans) % S;
			printf("%d\n",ans = Query(v,a));
		}
	}
	return 0;
}

评测结果