代码

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<algorithm>

#define ll long long
#define int long long
#define rg register
#define il inline
#define MX (601000 + 5)
#define INF (0x3f3f3f3f)

int max(int x ,int y){return x > y ? x : y;}
int min(int x ,int y){return x < y ? x : y;}

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

struct Edge{
	int u ,v ,h ,w;
	bool operator <(const Edge b)const{
		return h > b.h;
	}
}E[MX << 1];

struct edge{
	int next ,node ,w;
}D[MX << 1];

namespace dijkstra{
	struct Node{
		int pos ,dis;
		bool operator <(const Node &b)const{return dis > b.dis;}
	};
	int head[MX] ,tot;
	int dis[MX] ,vis[MX];
	void addedge(int u ,int v ,int w){
		D[++tot].next = head[u];
		head[u] = tot;
		D[tot].node = v;
		D[tot].w = w;
	}
	void init(){
		memset(head ,0 ,sizeof(head));
		tot = 0;
	}
	void dij(int st = 1){
		memset(dis ,0x3f ,sizeof(dis));
		memset(vis ,0 ,sizeof(vis));
		dis[st] = 0;
		std::priority_queue<Node> q;
		q.push((Node){st ,0});
		while(!q.empty()){
			Node now = q.top();
			q.pop();
			if(vis[now.pos])	continue;
			vis[now.pos] = true;
			for(rg int i = head[now.pos] ,d ; i ; i = D[i].next){
				d = D[i].node;
				if(dis[now.pos] + D[i].w < dis[d]){
					dis[d] = dis[now.pos] + D[i].w;
					if(!vis[d]){q.push((Node){d ,dis[d]});}
				}
			}
		}
	}
}

namespace tree{
	int head[MX] ,tot ,FA[MX][25];
	edge H[MX << 1];
	void addedge(int u ,int v ,int w = 0){
		H[++tot].next = head[u];
		head[u] = tot;
		H[tot].node = v ,H[tot].w = w;
	}
	int W[MX] ,check[MX];
	int dp[MX];
	void init(){
		memset(head ,0 ,sizeof(head));
		tot = 0;
		memset(FA ,0 ,sizeof(FA));
		memset(H ,0 ,sizeof(H));
		memset(W ,0 ,sizeof(W));
		memset(check ,0 ,sizeof(check));
		memset(dp ,0 ,sizeof(dp));
	}
	int dapai(int x){
		if(check[x])	return dp[x];
		int ans = INF;
		for(rg int i = head[x] ,d ; i ; i = H[i].next){
			d = H[i].node;
			ans = min(ans ,dapai(d));
		}
		ans = min(ans ,dijkstra::dis[x]);
		check[x] = true;
		return dp[x] = ans;
	}
	int getans(int st ,int lower){
		for(rg int i = 18 ; ~i ; --i){
			if(FA[st][i] == 0 || W[FA[st][i]] <= lower)	continue;
			st = FA[st][i];
		}
		return dapai(st);
	}
}

void init(){
	memset(fa ,0 ,sizeof(fa));
	memset(E ,0 ,sizeof(E));
	memset(D ,0 ,sizeof(D));
	dijkstra::init();
	tree::init();
}

int n ,m;

void solve(){
	init();
	using namespace dijkstra;
	scanf("%lld%lld" ,&n ,&m);
	for(rg int i = 1 ,u ,v ,w ,h ; i <= m ; ++i){
		scanf("%lld%lld%lld%lld" ,&u ,&v ,&w ,&h);
		E[i] = (Edge){u ,v ,h ,w};
		addedge(u ,v ,w);
		addedge(v ,u ,w);
	}
	dij();
	std::sort(E + 1 ,E + 1 + m);
	
	using namespace tree;
	int cnt = 1;
	for(rg int i = 1 ; i <= 2*n ; ++i)	fa[i] = i;
	for(rg int i = 1 ,u ,v ; i <= m ; ++i){
		if(cnt == n)	break;
		u = E[i].u ,v = E[i].v;
		int aimu = find(u) ,aimv = find(v);
		if(aimu != aimv){
			addedge(cnt + n ,aimu);
			addedge(cnt + n ,aimv);
			//std::cerr << cnt + n << " " << aimu << " \n";
			//sstd::cerr << cnt + n << " " << aimv << " \n";
			FA[aimu][0] = FA[aimv][0] = fa[aimu] = fa[aimv] = cnt + n;
			W[cnt + n] = E[i].h;
			//std::cerr << "Weight = " << E[i].h << " \n";
			++cnt;
		}
	}
	for(rg int i = 1 ; i <= 18 ; ++i){
		for(rg int j = 1 ; j <= n + n ; ++j){
			FA[j][i] = FA[FA[j][i - 1]][i - 1];
		}
	}
	for(int i = 1 ; i <= n ; ++i)	W[i] = INF;
	
	int q ,k ,s ,lastans = 0;
	scanf("%lld%lld%lld" ,&q ,&k ,&s);
	for(rg int i = 1 ,st ,p ; i <= q ; ++i){
		scanf("%lld%lld" ,&st ,&p);
		st = (st + k * lastans - 1) % n + 1;
		p = (p + k * lastans) % (s + 1);
		printf("%lld \n" ,lastans = getans(st ,p));
	}
}

signed main(){
	int t;
	scanf("%lld" ,&t);
	while(t--){
		solve();
	}return 0;
}

评测结果