代码

#include<bits/stdc++.h>
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define endl '\n'
#define int long long

int read()
{
	int x, t = 1;
	char c;
	while(c = getchar(), c < '0' || c > '9') if(c == '-') t = -1;
	x = c - '0';
	while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0';
	return x * t;
}

const int mmax = 4e5 + 10;
const int M = 8e5 + 10;
const int inf = 0x3f3f3f3f;

int test, n, m, q, k, s, lastans, first[mmax], tot, f[mmax], Tot, First[mmax];
int zx[mmax][20], dep[mmax], dis[mmax], vis[mmax];
struct node
{
	int u, v, l, a;
}e[M << 2], E[mmax << 2];
struct Node
{
	int v, w, nxt;
}g[M << 2];
struct Dij
{
	int v, w;
	bool operator < (const Dij &x) const {return x.w < w;}
};
struct tree
{
	int v, nxt;
}t[M << 2];

int find(int x) {return f[x] == x ? f[x] : f[x] = find(f[x]);}
int query(int x, int y)
{
	for(int i = 19;i >= 0;i--)
		if(dep[x] - (1 << i) >= 0 && E[zx[x][i]].a > y)
			x = zx[x][i];
	return E[x].l;
}

void add(int u, int v, int w)
{
	g[++tot].v = v;
	g[tot].w = w;
	g[tot].nxt = first[u];
	first[u] = tot;
	return;
}

void dfs(int cur, int fa)
{
	dep[cur] = dep[fa] + 1;
	zx[cur][0] = fa;
	for(int i = 1;(1 << i) <= dep[cur];i++)
		zx[cur][i] = zx[zx[cur][i-1]][i-1];
	for(int i = First[cur];i;i = t[i].nxt)
	{
		int v = t[i].v;
		if(v != fa) dfs(v, cur);
		E[cur].l = std::min(E[cur].l, E[v].l);
	}
	return;
}

void dij(int x)
{
	memset(vis, 0, sizeof vis);
	memset(dis, inf, sizeof dis);
	dis[x] = 0;
	std::priority_queue<Dij> q;
	q.push({x, 0});
	while(!q.empty())
	{
		Dij tmp = q.top();
		q.pop();
		if(vis[tmp.v]) continue;
		vis[tmp.v] = 1;
		for(int i = first[tmp.v];i;i = g[i].nxt)
		{
			int v = g[i].v;
			if(vis[v]) continue;
			if(dis[v] > dis[tmp.v] + g[i].w)
			{
				dis[v] = dis[tmp.v] + g[i].w;
				q.push({v, dis[v]});
			}
		}
	}
	for(int i = 1;i <= n;i++)
		E[i].l = dis[i];
	return;
}

void init()
{
	lastans = tot = Tot = 0;
	memset(first, 0, sizeof first);
	memset(First, 0, sizeof First);
	//memset(e, 0, sizeof e);
	//memset(E, 0, sizeof E);
	//memset(g, 0, sizeof g);
	//memset(t, 0, sizeof t);
	memset(zx, 0, sizeof zx);
	memset(dep, 0, sizeof dep);
	return;
}

void addt(int u, int v)
{
	t[++Tot].v = v;
	t[Tot].nxt = First[u];
	First[u] = Tot;
	return;
}

void krus()
{
	for(int i = 1;i <= (n << 1);i++)
		f[i] = i;
	std::sort(e+1, e+m+1, [](node x, node y) {return x.a > y.a;});
	int cnt = n, ttot = 0;
	for(int i = 1;i <= m;i++)
	{
		int fx = find(e[i].u), fy = find(e[i].v);
		if(fx != fy)
		{
			int now = ++cnt;
			//val[now] = edge[i].w;
			f[fx] = f[fy] = f[now] = now;
			addt(now, fx);
			addt(now, fy);
			E[cnt].a = e[i].a;
			ttot++;
		}
		if(ttot == n-1) break;
	}
	dfs(cnt, 0);
	while(q--)
	{
		int x = (k * lastans + read() - 1) % n + 1, y = (k * lastans + read()) % (s + 1);
		std::cout << (lastans = query(x, y)) << endl;
	}
	return;
}

signed main()
{
	//ioclear;
	test = read();
	while(test--)
	{
		init();
		n = read();
		m = read();
		for(int i = 1;i <= m;i++)
		{
			std::cin >> e[i].u >> e[i].v >> e[i].l >> e[i].a;
			add(e[i].u, e[i].v, e[i].l);
			add(e[i].v, e[i].u, e[i].l);
		}
		for(int i = 1;i <= (n << 1);i++)
			E[i].l = inf;
		dij(1);
		q = read(), k = read(), s = read();
		krus();
	}
}

评测结果