代码

#include<queue>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 6e5 + 10;

struct E {
	int u, v, l, a;
	bool operator < (const E& A) const { return a > A.a; }
} e[maxn];

struct Edge {
	Edge* next;
	int to, w;
	Edge(Edge* next = 0, int to = 0, int w = 0): next(next), to(to), w(w) {}
} *first[maxn], *f2[maxn];

int n, m, f[maxn], d[maxn], vis[maxn], de[maxn], c, q, k, s, vi[maxn][20], pi[maxn][20];

int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

struct Node {
	int u, w;
	Node(int u = 0, int w = 0): u(u), w(w) {}
	bool operator < (const Node& A) const { return w > A.w; }
};

void Dijkstra() {
	priority_queue<Node> Q; Q.push(Node(1, 0));
	memset(d, 0x3f, sizeof d), d[1] = 0;
	memset(vis, 0, sizeof vis);
	while (!Q.empty()) {
		Node x = Q.top(); Q.pop();
		if (vis[x.u]) continue;
		vis[x.u] = 1;
		for (Edge* now = first[x.u]; now; now = now->next) {
			if (d[now->to] > d[x.u] + now->w) {
				d[now->to] = d[x.u] + now->w;
				Q.push(Node(now->to, d[now->to]));
			}
		}
	}
}

void Add(int u, int v, int w) {
	f2[u] = new Edge(f2[u], v, w);
	f2[v] = new Edge(f2[v], u, w);
}

void Dfs(int u, int pa) {
	for (int i = 1; (1 << i) <= c; i++) pi[u][i] = pi[pi[u][i - 1]][i - 1];
	for (int i = 1; (1 << i) <= c; i++) vi[u][i] = min(vi[u][i - 1], vi[pi[u][i - 1]][i - 1]);
	for (Edge* now = f2[u]; now; now = now->next) {
		if (now->to == pa) continue;
		pi[now->to][0] = u, vi[now->to][0] = now->w;
		de[now->to] = de[u] + 1, Dfs(now->to, u);
		d[u] = min(d[u], d[now->to]);
	}
}

inline int read() {
	int x = 0;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar());
	for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + ch - 48;
	return x;
}

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		memset(first, 0, sizeof first);
		memset(f2, 0, sizeof f2);
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; i++) {
			e[i].u = read(), e[i].v = read(), e[i].l = read(), e[i].a = read();
			first[e[i].u] = new Edge(first[e[i].u], e[i].v, e[i].l);
			first[e[i].v] = new Edge(first[e[i].v], e[i].u, e[i].l);
		}
		Dijkstra();
		sort(e + 1, e + 1 + m);
		for (int i = 1; i <= n << 1; i++) f[i] = i;
		c = n;
		for (int i = 1; i <= m; i++) {
			int u = find(e[i].u), v = find(e[i].v);
			if (u == v) continue;
			Add(++c, u, e[i].a), Add(c, v, e[i].a);
			f[u] = f[v] = c;
		}
		memset(pi, 0, sizeof pi);
		de[c] = 1, Dfs(c, 0);
		int ans = 0;
		scanf("%d%d%d", &q, &k, &s);
		while (q--) {
			int v = read(), p = read();
			v = (v + 1ll * k * ans - 1) % n + 1;
			p = (p + 1ll * k * ans) % (s + 1);
			for (int i = 19; ~i; i--) {
				if (de[v] - (1 << i) > 0 && vi[v][i] > p) {
					v = pi[v][i];
				}
			}
			printf("%d\n", ans = d[v]);
		}
	}
	return 0;
}

评测结果