代码

#include<cstdio>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
inline int read() {
	char c = getchar(); int x = 0, f = 1;
	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
	return x * f;
}
int N, M, lastans;
struct Edge {
	int u, v, l, a, t, nxt;
}E[MAXN];
int head[MAXN], num = 1;
int dis[MAXN], vis[MAXN];
void init() {
	memset(head, -1, sizeof(head));
	num = 1;
	memset(vis, 0, sizeof(vis));
	lastans = 0;
}
void AddEdge(int x, int y, int z, int GG) {
	E[num] = (Edge){x, y, z, GG, 0, head[x]};
	head[x] = num++;
}
void SPFA(int S) {
	memset(dis, 0x3f, sizeof(dis));
	dis[S] = 0; 
	queue<int> q; q.push(S);
	while(!q.empty()) {
		int p = q.front(); q.pop(); vis[p] = 0;
		for(int i = head[p]; i != -1; i = E[i].nxt) {
			int to = E[i].v;
			if(dis[to] > dis[p] + E[i].l) {
				dis[to] = dis[p] + E[i].l;
				if(!vis[to]) 
					q.push(to), vis[to] = 1;
			}
		}
	}
}
void dfs(int now, int hi, int ti) {
	vis[now] = ti; 
	lastans = min(lastans, dis[now]);
	for(int i = head[now]; i != -1; i = E[i].nxt) {
		int to = E[i].v;
		if(vis[to] == ti) continue;
		if(E[i].a <= hi) continue;
		dfs(to, hi, ti);
	}
}
int main() {

	int QwQ = read();
	while(QwQ--) {
		init();
		N = read(); M = read();
		for(int i = 1; i <= M; i++) {
			int x = read(), y = read(), z = read(), GG = read();
			AddEdge(x, y, z, GG);
			AddEdge(y, x, z, GG);
		}
		SPFA(1);
		int Q = read(), K = read(), S = read();
		for(int i = 1; i <= Q; i++) {
			int v = read(), p = read();
			v = (v + K * lastans - 1) % N + 1;
			p = (p + K * lastans) % (S + 1);
			lastans = INF; dfs(v, p, i);
			printf("%d\n", lastans);
		}
	}
	return 0;
}
/*
1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2
*/

评测结果