代码

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(a) a.begin(), a.end()
#define lowbit(x) ((x) & -(x))

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, int> pii;
typedef pair<int, int> pi;
typedef vector<int> VI;

namespace io {
	const int L = (1 << 21) + 1;
	char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, qu[55]; int f, qr;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, L, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; }
	inline void putc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	template <class I> inline void gi (I & x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	template <class I> inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0', x /= 10;
		while (qr) putc (qu[qr --]);
	}
	inline char read () {
		for (c = gc(); c < 'a' || c > 'z'; c = gc());
		return c;
	}
	inline void gs (char *s) {
		int l;
		for (c = gc(); c < 'a' || c > 'z'; c = gc());
		for (l = 0; c <= 'z' && c >= 'a'; c = gc()) s[l] = c, ++l;
		s[l] = 0;
	}
	inline void ps (const char *s) {
		int l = strlen(s), i;
		for (i = 0; i < l; i ++) putc(s[i]);
	}
	struct IOC { ~ IOC () { flush (); } } _ioc_;
} ;
using io::gi;
using io::gs;
using io::ps;
using io::putc;
using io::read;
using io::print;

template <class T> inline bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
template <class T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }

const int N = 2e5 + 5, M = 4e5 + 5, inf = 2e9, G = 20;

struct edge_t{
	int u, v, c;
	edge_t() { u = v = c = 0; }
	edge_t(int u, int v, int c):u(u), v(v), c(c) {}
	bool operator < (const edge_t &a) const { return c < a.c; }
} ;

vector <pi> adj[N];
vector <edge_t> all;
priority_queue <pi, vector<pi>, greater<pi> > Q;
int ans, test, n, m, cnt, q, op, hi, dis[N], fa[M][G], tim[M], res[M], par[M];
int find(int u){ return par[u] == u ? u : par[u] = find(par[u]); }
bool vis[N];

int main(){
	freopen("return.in", "r", stdin), freopen("return.out", "w", stdout);
	for (gi(test); test; --test) {
		int i, u, v, l, a;
		gi(n), gi(m);
		for (i = 1; i <= m; i ++) {
			gi(u), gi(v), gi(l), gi(a);
			adj[u].pb(pi(v, l)), adj[v].pb(pi(u, l));
			all.pb(edge_t(u, v, -a));
		}
		for (i = 1; i <= n; i ++) dis[i] = inf;
		Q.push(pi(dis[1] = 0, 1));
		while (Q.size()) {
			pi cur = Q.top(); Q.pop();
			if (vis[u = cur.se]) continue;
			vis[u] = true;
			for (i = 0; i < adj[u].size(); i ++) {
				pi e = adj[u][i];
				if (dis[v = e.fi] > dis[u] + e.se) {
					dis[v] = dis[u] + e.se;
					Q.push(pi(dis[v], v));
				}
			}
		}
		for (i = 1; i <= n; i ++) par[i] = i, res[i] = dis[i], tim[i] = -inf;
		cnt = n;
		sort(all.begin(), all.end());
		for (i = 0; i < all.size(); i ++) {
			u = find(all[i].u), v = find(all[i].v);
			if (u == v) continue;
			++cnt, fa[u][0] = par[u] = cnt, fa[v][0] = par[v] = cnt, par[cnt] = cnt;
			tim[cnt] = all[i].c, res[cnt] = min(res[u], res[v]);
		}
		for (u = cnt; u >= 1; u --) for (i = 0; fa[u][i]; fa[u][i + 1] = fa[fa[u][i]][i], ++i);
		for (ans = 0, gi(q), gi(op), gi(hi); q; q --) {
			gi(u), gi(v);
			u = (u + op * ans - 1) % n + 1;
			if (u <= 0) u += n;
			v = (v + op * ans) % (hi + 1);
			for (i = 18; i >= 0; i --) if (tim[fa[u][i]] < -v) u = fa[u][i];
			print(ans = res[u]), putc('\n');
		}
		
		all.clear();
		for (u = 1; u <= n; u ++) adj[u].clear(), dis[u] = vis[u] = 0;
		for (u = 1; u <= cnt; u ++) {
			par[u] = res[u] = tim[u] = 0;
			memset(fa[u], 0, sizeof(fa[u]));
		}
	}
	return 0;
}

评测结果