代码

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define se second
using namespace std;
#define int long long

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
const int MAXN = 4e5+100;
const int MAXQ = 4e5+100;

///------------------head------------------
int T,n,m,Q,K,S,head[MAXN],cnt=0,inf,lastans=0,sz=0;
int dist[MAXN],vis[MAXN],isq[MAXN],t[MAXN<<1];
struct Edges{
    int to,nxt,l,a;
}E[MAXN<<1];
struct Node{
    int u,v,l,a;
    bool operator < (const Node &b) const {
        return a > b.a;
    }
    Node(int uu=0,int vv=0,int ll=0,int aa=0):u(uu),v(vv),l(ll),a(aa){}
}M[MAXN<<1];
int root[MAXN<<1], L[MAXN<<6], R[MAXN<<6];
struct rop{
    int v,s,m;
    rop(int vv=0,int ss=0,int mm=0):v(vv),s(ss),m(mm){}
}sub[MAXN<<1];
inline void copy(int &n, int N) {
	int g = ++sz;
	sub[g] = sub[N];
	L[g] = L[N];
	R[g] = R[N];
	n = g;
}
inline void build_(int &n,int l,int r){
    n = ++sz;
    if (!(l-r)) {sub[n]=(rop){l,1,dist[l]}; return;}
    int m = (l+r) >> 1;
    build_(L[n],l,m);
    build_(R[n],m+1,r);
}
inline void build(int &n, int l, int r) {
	n = ++sz;
	if (l == r) return sub[n] = rop(l, 1, dist[l]), void();
	int mid = (l + r) >> 1;
	build(L[n], l, mid);
	build(R[n], mid + 1, r);
}
inline rop query(int n, int l, int r, int p) {
	if (l == r) return sub[n];
	int mid = (l + r) >> 1;
	if (p <= mid) return query(L[n], l, mid, p);
	return query(R[n], mid + 1, r, p);
}
inline void Modify(int &n, int N, int l, int r, int p, rop v) {
	copy(n, N);
	if (l == r) return sub[n] = v, void();
	int mid = (l + r) >> 1;
	if (p <= mid) return Modify(L[n], L[N], l, mid, p, v);
	return Modify(R[n], R[N], mid + 1, r, p, v);
}
inline int find(int x, int tsp) {
	for (int y = query(root[tsp], 1, n, x).v; x != y; y = query(root[tsp], 1, n, x).v) x = y;
	return x;
}
inline void SPFA(int u){
    MM(isq,0);
    dist[u] = 0;
    isq[u] = 1;
    queue<int>Q;
    Q.push(u);
    while(!Q.empty()){
        int frt = Q.front();
        Q.pop();
        for (int i = head[frt]; i; i = E[i].nxt){
            int v = E[i].to,w = E[i].l;
            if (dist[frt] +  w < dist[v]) {
                dist[v] = dist[frt] + w;
                if (!isq[v])
                Q.push(v),isq[v]=1;
            }
        }
        isq[frt] = 0;
    }
}
inline void addedge(int u,int v,int l,int a){E[++cnt].nxt = head[u]; E[cnt].to = v; E[cnt].l = l; E[cnt].a = a; head[u] = cnt;}
signed main(signed argc, char *argv[]){
    //freopen("return.in","r",stdin);
    //freopen("return.out","w",stdout);
    T=read();
    while(T--){
        MM(head,0);cnt=0;MM(dist,0x7f);sz=0;
        n=read(),m=read();
        rep(i,1,m)
        {
            int u=read(),v=read(),l=read(),a=read();
            M[i] = Node(u,v,l,a);
            addedge(u,v,l,a); addedge(v,u,l,a);
        }
        SPFA(1);
        sort(M+1,M+m+1);
        Q=read(),K=read(),S=read();
        build(root[0],1,n);
        for (int i = 1; i <= m; i++) {
			int u = M[i].u, v = M[i].v;
			int U = find(u, i - 1),V = find(v, i - 1);
			if (U == V)
				root[i] = root[i - 1];
			else
            {
				rop uu = query(root[i - 1], 1, n, U),vv = query(root[i - 1], 1, n, V);
				if (uu.s < vv.s) {
					swap(uu, vv);
					swap(U, V);
				}
				vv.v = U;
				uu.s += vv.s;
				uu.m = min(uu.m, vv.m);
				Modify(root[i], root[i - 1], 1, n, V, vv);
				Modify(root[i], root[i], 1, n, U, uu);
			}
		}
        lastans = 0;
        while(Q--){
            int v0=read(),p0=read();
            int v=(v0 + K * lastans - 1) % n + 1;
            int p=(p0 + K * lastans) % (S+1);
            int l = 1, r = m, ans = 0;
			while (l <= r) {
				int mid = (l + r) >> 1;
				if (M[mid].a > p)
					ans = mid, l = mid + 1;
				else
					r = mid - 1;
			}
            int V = find(v,ans);
            rop cur = query(root[ans],1,n,V);
            lastans = cur.m;
            printf("%lld\n",lastans);
        }
    }
    return 0;
}

/* Examples: */
/*

*/

/*

*/

评测结果