代码

/*program by mangoyang*/
#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<algorithm>
#include<queue>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define int ll
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int f = 0, ch = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
const int N = 200005, M = 800005;
int n, m, Q, K, S;

int a[M], b[M], nxt[M], head[N], dis[N], cnt;
struct Node{ 
	ll d, id;
	bool operator < (const Node &A) const{ return d > A.d; }
}; priority_queue<Node> pq;
inline void add(int x, int y, int z){
	a[++cnt] = y, b[cnt] = z, nxt[cnt] = head[x], head[x] = cnt;
}
inline void dijkstra(){
	for(int i = 1; i <= n; i++) dis[i] = inf / 3;
	dis[1] = 0, pq.push((Node){0, 1});
	while(!pq.empty()){
		Node now = pq.top(); pq.pop();
		int val = now.d, u = now.id;
		if(dis[u] < val) continue;
		for(int p = head[u]; p; p = nxt[p]){
			int v = a[p];
			if(dis[u] + b[p] < dis[v]){
				dis[v] = dis[u] + b[p];
				pq.push((Node){dis[v], v});
			}
		} 
	} 
}

struct PersistableArray{
	int rt[N], s[(N+M)*25], lc[(N+M)*25], rc[(N+M)*25], size;
	inline void clear(){
		for(int i = 1; i <= size; i++) lc[i] = rc[i] = s[i] = 0;
		for(int i = 1; i <= n; i++) rt[i] = 0; size = 0;
	}
	inline void build(int &u, int l, int r, int *a){
		u = ++size;
		if(l == r) return (void) (s[u] = a[l]);
		int mid = l + r >> 1;
		build(lc[u], l, mid, a), build(rc[u], mid + 1, r, a);
	}	
	inline void Ins(int &u, int pr, int l, int r, int pos, int v){
		u = ++size;
		if(l == r) return (void) (s[u] = v);
		int mid = l + r >> 1; 
		lc[u] = lc[pr], rc[u] = rc[pr];
		if(pos <= mid) Ins(lc[u], lc[pr], l, mid, pos, v);
		else Ins(rc[u], rc[pr], mid + 1, r, pos, v);
	}
	inline int query(int u, int l, int r, int pos){
		if(l == r) return s[u];
		int mid = l + r >> 1;
		if(pos <= mid) return query(lc[u], l, mid, pos);
		else return query(rc[u], mid + 1, r, pos);
	}
	inline int get(int u, int pos){ return query(rt[u], 1, n, pos); }
	inline void mof(int u, int pos, int v){ Ins(rt[u], rt[u], 1, n, pos, v); }
}fa, sz;

namespace Dsu{
	int a[N], ban;
	inline int ask(int now, int x){
		int p = fa.get(now, x);
		if(p <= 0) return x; else return ask(now, p);
	}
	inline void unite(int x, int y){
		int p = ask(ban, x), q = ask(ban, y);
		if(p == q) return;
		//cout << "Realunite :" << x << " " << y << endl; 
		int szp = sz.get(ban, p), szq = sz.get(ban, q);
		if(szp > szq) swap(p, q);
		int vap = fa.get(ban, p), vaq = fa.get(ban, q);
		//cout << vap << " " << vaq << endl;
		fa.mof(ban, p, q), fa.mof(ban, q, Max(vap, vaq));
		sz.mof(ban, q, szp + szq); 
	}
	inline void addban(){ 
		fa.rt[ban+1] = fa.rt[ban];
		sz.rt[ban+1] = sz.rt[ban], ban++; 
	}
	inline void prepare(){
		ban = 0;
		for(int i = 1; i <= n; i++) a[i] = -dis[i];
		fa.build(fa.rt[0], 1, n, a);
		for(int i = 1; i <= n; i++) a[i] = 1;
		sz.build(sz.rt[0], 1, n, a);
	}
}

int hs[N], c[N];
struct Edge{ int x, y, a; } e[M];
inline bool cmp(Edge A, Edge B){ return A.a < B.a; }
inline void solve(int l, int r){
	Dsu::addban();
	for(int i = l; i <= r; i++) hs[i] = Dsu::ban;
	for(int i = l; i <= r; i++) Dsu::unite(e[i].x, e[i].y);
}
inline void BuildDsu(){
	sort(e + 1, e + m + 1, cmp), e[0].a = e[m+1].a = -1;
	Dsu::prepare();
	for(int i = m, r; i >= 1; i--){
		if(e[i].a != e[i+1].a) r = i;
		if(e[i].a != e[i-1].a) solve(i, r);
	}
	hs[m+1] = 0;
	for(int i = 1; i <= m; i++) c[i] = e[i].a;
	//cout << endl;
	//for(int i = 1; i <= m; i++) cout << c[i] << " "; cout << endl;
	//for(int i = 1; i <= m; i++) cout << hs[i] << " "; cout << endl;
}
inline int query(int u, int p){
	int pos = upper_bound(c + 1, c + m + 1, p) - c;
	//cout << "his = " << hs[pos] << endl;
	int rt = Dsu::ask(hs[pos], u); return -fa.get(hs[pos], rt); 
}

inline void cleartype(){
	#define mem(x) memset(x, 0, sizeof(x))
	fa.clear(), sz.clear();
	mem(a), mem(b), mem(nxt), mem(head), cnt = 0;
}
inline void init(){
	read(n), read(m);
	for(int i = 1, x, y, z, a; i <= m; i++){
		read(x), read(y), read(z), read(a);
		add(x, y, z), add(y, x, z), e[i] = (Edge){x, y, a};
	}
	read(Q), read(K), read(S);
}
inline void realmain(){
	cleartype(), init(), dijkstra(), BuildDsu();
	int lastans = 0;
	while(Q--){
		int u, p; read(u), read(p);
		p = (p + K * lastans) % (S + 1);
		u = (u + K * lastans - 1) % n + 1;
		printf("%d\n", lastans = query(u, p));
	}
}	
main(){
	int T; read(T); while(T--) realmain();
	return 0;
}

评测结果