代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define pii pair<ll,int>
#define fi first
#define se second
const int N = 400002, M = 1000002;
typedef long long ll;
template <class T>inline void read(T &x) {
	x=0; int f=1; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	x*=f;
}
int cnt, nxt[M], head[N], to[M], w[M];
#define add(u,v,l) (nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,w[cnt]=l)
#define add2(u,v) (nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v)
#define clear_Edge (memset(head,0,sizeof head),cnt=0)
#define travel(u) for(re i=head[u];i;i=nxt[i])
struct Edge {
	int u, v, H;
	inline bool operator < (const Edge &rhs)const{return H>rhs.H;}
} e[M];
int fa[N];
int find(int x){return !fa[x]?x:fa[x]=find(fa[x]);}

priority_queue<pii,vector<pii>,greater<pii> > q;
ll dis[N]; bool vis[N];
inline void Dijkstra() {
	memset(vis, 0, sizeof vis); memset(dis, 0x7f, sizeof dis); dis[1]=0;
	q.push(make_pair(0,1));
	int v;
	while(!q.empty()) {
		pii u=q.top(); q.pop();
		if(vis[u.se])	continue;
		vis[u.se]=1;
		travel(u.se) { v = to[i];
			if(dis[v] > u.fi+w[i]) {
				dis[v] = u.fi+w[i];
				q.push(make_pair(dis[v],v));
			}
		}
	}
}

int T, n, m, id, H[N], f[N][21];
ll d[N], lastans;
void dfs(int u) {
	travel(u)
		dfs(to[i]),f[to[i]][0]=u,d[u]=min(d[u],d[to[i]]);
	if(u<=n)	d[u]=dis[u];
}
inline void init() {rep(j,1,20)rep(i,1,id)f[i][j]=f[f[i][j-1]][j-1];}
inline void rec() {
	clear_Edge; memset(fa,0,sizeof fa);
	rep(i,1,m) {
		int p=find(e[i].u), q=find(e[i].v);
		if(p!=q) {
			fa[p]=fa[q]=++id; // new Node
			add2(id,p), add2(id,q); //Kruskal重构树
			H[id] = e[i].H;
		}
	}
	memset(d,0x7f,sizeof d); dfs(id); init();
}
int main() {
	static int u, v, l, a, Q, K, S, p;
	read(T);
	while(T--) {
		read(n), read(m); id=n; clear_Edge;
		rep(i,1,m) {
			read(u),read(v),read(l),read(a);
			add(u,v,l); add(v,u,l); e[i]=(Edge){u,v,a};
		}
		sort(e+1, e+m+1);
		Dijkstra();  rec();

		read(Q), read(K), read(S); lastans=0;
		while(Q--) {
			read(v), read(p);
			v = (v+K*lastans-1)%n+1;
			p = (p+K*lastans)%(S+1);
			for(int i=20;i>=0;--i)	if(H[f[v][i]]>p)v=f[v][i];
			printf("%lld\n", lastans=d[v]);
		}
	}
	return 0;
}

评测结果