代码

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
    int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * fh;
}

void File() {
	freopen ("return.in", "r", stdin);
	freopen ("return.out", "w", stdout);
}

int n, m;

const int N = 8e5 + 1e3, M = 8e5 + 1e3;

struct Edge {
	int u, v, a;

	inline bool operator < (const Edge &rhs) const {
		return a > rhs.a;
	}

} lt[N];

namespace Union_Set {

	int val[N], fa[N];

	void Init(int *bas) {
		For (i, 1, n) fa[i] = i, val[i] = bas[i];
	}

	int find(int x) { 
		return x == fa[x] ? x : fa[x] = find(fa[x]); 
	}

	inline void Union(int x, int y) {
		int rtx = find(x), rty = find(y);
		if (rtx == rty) return ;
		chkmin(val[rty], val[rtx]);
		fa[rtx] = rty;
	}

	inline int Get_Val(int x) { int rtx = find(x); return val[rtx]; }

}

typedef pair<int, int> PII;
#define fir first
#define sec second
#define mp make_pair

namespace Dijsktra {

	int Head[N], Next[M], to[M], val[M], e = 0;

	void Init() { Set(Head, 0); e = 0; }

	inline void add_edge(int u, int v, int w) { to[++ e] = v; Next[e] = Head[u]; val[e] = w; Head[u] = e; }

	priority_queue<PII, vector<PII>, greater<PII> > P; 
	bool vis[N]; int dis[N];
	void Run() {
		Set(vis, false);
		Set(dis, 0x7f); dis[1] = 0; P.push(mp(0, 1));
		while (!P.empty()) {
			PII cur = P.top(); int u = cur.sec; P.pop();
			if (vis[u]) continue ; 
			vis[u] = true;

			for (int i = Head[u]; i; i = Next[i]) {
				int v = to[i];
				if (chkmin(dis[v], dis[u] + val[i])) 
					P.push(mp(dis[v], v));
			}
		}
	}

}

int q, k, s;

namespace Off_Line {

	struct Ask {

		int v, p, id;

		inline bool operator < (const Ask &rhs) const { return p > rhs.p; }

	} Q[N];

	int ans[N];
	void Solve() {

		For (i, 1, q) {
			int v = read(), p = read();
			Q[i] = (Ask) {v, p, i};
		}

		sort(Q + 1, Q + 1 + q);

		int cur = 1;
		For (i, 1, m) {
			while (cur <= q && Q[cur].p >= lt[i].a) { ans[Q[cur].id] = Union_Set :: Get_Val(Q[cur].v); ++ cur; }
			Union_Set :: Union(lt[i].u, lt[i].v);
		}
		while (cur <= q) { ans[Q[cur].id] = Union_Set :: Get_Val(Q[cur].v); ++ cur; }

		For (i, 1, q)
			printf ("%d\n", ans[i]);
	}

}

namespace In_Line {

	void Solve() {

		int ans = 0;
		For (i, 1, q) {
			int v = (read() + ans + n - 1) % n + 1, p = (read() + ans) % (s + 1);
			Union_Set :: Init(Dijsktra :: dis);

			For (j, 1, m) {
				if (lt[j].a <= p) break;
				Union_Set :: Union(lt[j].u, lt[j].v);
			}
			ans = Union_Set :: Get_Val(v);
			printf ("%d\n", ans);
		}

	}
}

int main () {

	int cases = read();
	while (cases --) {

		n = read(); m = read();

		Dijsktra :: Init();

		For (i, 1, m) {
			int u = read(), v = read(), l = read(), a = read();
			lt[i] = (Edge) {u, v, a};
			Dijsktra :: add_edge(u, v, l);
			Dijsktra :: add_edge(v, u, l);
		}
		Dijsktra :: Run();

		sort(lt + 1, lt + 1 + m);
		Union_Set :: Init(Dijsktra :: dis);

	//	For (j, 1, n) printf ("%d%c", Dijsktra :: dis[j], j == jend ? '\n' : ' ');
		
		q = read(); k = read(); s = read();
		if (!k) Off_Line :: Solve();
		else In_Line :: Solve();

	}

	return 0;
}

评测结果