代码

#include <bits/stdc++.h>

using namespace std;
namespace DEBUG {
	void debug_out() { cerr << '\n'; }
	template <typename Head, typename... Tail>
	void debug_out(Head H, Tail... T) { cerr << ' ' << H, debug_out(T...); }
	#define debug(...) cerr << '[' << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
} using namespace DEBUG;
namespace fastIO {
	char B[1 << 16], *S = B, *T = B;
	inline char getchar() { return S == T && (T = (S = B) + fread(B, 1, 1 << 16, stdin), S == T) ? EOF : *S++; }
	template<typename Tp> inline void read(Tp &o) {
		o = 0; bool s = 0; char c = getchar();
		while(c > '9' || c < '0') s |= c == '-', c = getchar();
		while(c >= '0' && c <= '9') o = o * 10 + c - '0', c = getchar();
		if(s) o = -o;
	}
} using fastIO::read;
template<typename T> inline void cmin(T &a, T b) { if(a > b) a = b; }
typedef long long ll;
#define eb emplace_back
#define all(x) x.begin(), x.end()
const int N = 2e5 + 5;
int T, n, m, Q, K, S;
struct edge {
	int u, v, l, a;
};
vector<edge> g[N];
vector<edge> edges;
int dis[N], vis[N];
struct node {
	int dis, id;
	bool operator<(const node &x) const {
		return dis > x.dis;
	}
};
priority_queue<node> q;
// disµÃ·À±¬£¡ 
void dijkstra() {
	for(int i = 1; i <= n; i++) dis[i] = 2e9, vis[i] = false;
	dis[1] = 0, q.push(node{0, 1});
	while(!q.empty()) {
		int u = q.top().id;
//		debug(u);
		q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(edge &e : g[u]) {
			int v = e.v, w = e.l;
			if(dis[v] > (ll)dis[u] + w) {
				dis[v] = dis[u] + w;
				if(!vis[v]) q.push(node{dis[v], v});
			}
		}
	}
//	for(int i = 1; i <= n; i++) debug(i, dis[i]);
}
// kruskalÖع¹Ê÷ Á½±¶½Úµã 
// DSU ²»ÄÜÆô·¢Ê½ºÏ²¢£¬ÒòΪÿ¸öµãµÄ¸¸Ç×±ØÐëÊÇËüÄǸö¶ÑµÄ¶¥ 
struct DSU {
	int fa[N * 2];
	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
	DSU() {
		for(int i = 1; i <= 2 * n; i++) fa[i] = i;
	}
}; 
// Á½±¶½ÚµãºóµÄlog 
int cnt, val[N * 2], fa[N * 2][20], minv[N * 2];
vector<int> g2[N * 2];
void kruskal() {
	sort(all(edges), [&](const edge &a, const edge &b) {
		return a.a > b.a;
	});
	DSU S;
	cnt = n;
	for(edge &e : edges) {
		int x = S.find(e.u), y = S.find(e.v);
		if(x == y) continue;
		val[++cnt] = e.a;
		g2[cnt].eb(x), g2[cnt].eb(y);
		S.fa[x] = cnt, S.fa[y] = cnt;
		if(cnt == 2 * n - 1) break;
	}
}
void dfs(int u, int f) {
	minv[u] = (u <= n) ? dis[u] : 2e9;
	fa[u][0] = f;
	for(int i = 1; fa[u][i - 1]; i++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(int v : g2[u])
		dfs(v, u), cmin(minv[u], minv[v]);
}
int query(int v, int p) {
	int now = v;
	for(int i = 19; i >= 0; i--)
		if(fa[now][i] && val[fa[now][i]] > p) now = fa[now][i];
	return minv[now];
}
void clear() {
	for(int i = 1; i <= n; i++) g[i].clear();
	for(int i = 1; i <= 2 * n; i++) g2[i].clear();
	memset(fa, 0, sizeof fa);
	edges.clear();
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	for(read(T); T; T--) {
		// ¶à²âÇå¿Õ 
		read(n), read(m);
		clear();
		for(int i = 1, u, v, l, a; i <= m; i++) {
			read(u), read(v), read(l), read(a);
			g[u].eb(edge{u, v, l, a}), g[v].eb(edge{v, u, l, a});
			edges.eb(edge{u, v, l, a});
		}
		dijkstra();
		kruskal();
		dfs(cnt, 0);
		read(Q), read(K), read(S);
		int ans = 0;
		for(int i = 1, v, p; i <= Q; i++) {
			read(v), read(p);
			v = (v + K * ans - 1) % n + 1, p = (p + K * ans) % (S + 1);
			cout << (ans = query(v, p)) << '\n';
		}
	}

	return 0;
}

评测结果