代码

#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cstdlib>

#include <algorithm>
#include <numeric>
#include <limits>
#include <functional>
#include <stack>
#include <vector>
#include <set>
#include <map>
#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, l, a;
	
	bool operator>(const Node& rhs) const { return a > rhs.a; }
};

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

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; }
};

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

int n, m;
int dis[N], f[N * 2], ht[N * 2], sub[N * 2];
int prt[N * 2][LGN];

Node ed[M];

Edge* g[N];

Edge pool[M * 2];
Edge* ptop;

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

void adde(int u, int v, int w);
void solve();

int main() {
#ifdef LBT
	freopen("test.in", "r", stdin);
	int nol_cl = clock();
#endif
	
	int t;
	scanf("%d", &t);
	while (t--)
		solve();
	
#ifdef LBT
	LOG("Time: %dms\n", int((clock() - nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
	return 0;
}

void solve() {
	memset(g, 0, sizeof(g));
	ptop = pool;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d%d", &ed[i].u, &ed[i].v, &ed[i].l, &ed[i].a);
		adde(ed[i].u, ed[i].v, ed[i].l);
		adde(ed[i].v, ed[i].u, ed[i].l);
	}
	sort(ed + 1, ed + m + 1, greater<Node>());
	
	priority_queue<Nde, vector<Nde>, greater<Nde> > heap;
	memset(dis, -1, sizeof(dis));
	heap.push(Nde(1, dis[1] = 0));
	while (!heap.empty()) {
		Nde tmp = heap.top();
		heap.pop();
		if (tmp.step != dis[tmp.u])
			continue;
		for (Edge* p = g[tmp.u]; p; p = p->next)
			if (dis[p->v] == -1 || dis[p->v] > tmp.step + p->w)
				heap.push(Nde(p->v, dis[p->v] = tmp.step + p->w));
	}
	
	iota(f + 1, f + n * 2, 1);
	memcpy(sub, dis, sizeof(dis));
	int cnt = n;
	for (int i = 1; i <= m; ++i) {
		int u = find(ed[i].u), v = find(ed[i].v);
		if (u == v)
			continue;
		f[u] = ++cnt;
		f[v] = cnt;
		prt[u][0] = cnt;
		prt[v][0] = cnt;
		sub[cnt] = min(sub[u], sub[v]);
		ht[cnt] = ed[i].a;
	}
	prt[cnt][0] = 0;
	for (int i = n * 2 - 1; i; --i)
		for (int j = 1; j < LGN; ++j)
			prt[i][j] = prt[prt[i][j - 1]][j - 1];
	
	int q, k, s;
	scanf("%d%d%d", &q, &k, &s);
	int lans = 0;
	while (q--) {
		int v, p;
		scanf("%d%d", &v, &p);
		v = (v + k * (lans % n) - 1) % n + 1;
		p = (p + k * (lans % (s + 1))) % (s + 1);
		for (int i = LGN - 1; i >= 0; --i)
			if (ht[prt[v][i]] > p)
				v = prt[v][i];
		printf("%d\n", lans = sub[v]);
	}
}

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

评测结果