代码

#include<cmath>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;

char getchar_ () {
	static char *s=new char[500000];
	static char *tail=s,*p=s;
	return p==tail&&((p=s)==(tail=s+fread(s,1,500000,stdin)))?-1:*p++;
}

void read_int (int &a) {
	static char c; c=getchar_(); a=0;
	while (c<'0'||c>'9') c=getchar_();
	while (c>='0'&&c<='9') a=(a<<1)+(a<<3)-48+c,c=getchar_();
}

void write_int (int a) {
	if (!a) { putchar(48); putchar('\n'); return; }
	static int *s=new int[10],*p;
	p=s; while (a) *p=a%10,++p,a/=10;
	while (p--!=s) putchar(*p+48);
	putchar('\n'); return;
}

const int MAXN=2e5,MAXM=4e5;

struct node {
	int point,next,value;
} r[MAXM*2+1];
int last[MAXN+1],tot;

struct relation {
	int u,v,value;
	bool operator < (const relation &p) const {
		return value>p.value;
	}
} d[MAXM+1];

void link (int u,int v,int value) {
	r[++tot].point=v;r[tot].next=last[u];r[tot].value=value;last[u]=tot;
	r[++tot].point=u;r[tot].next=last[v];r[tot].value=value;last[v]=tot;
}

int T,n,m,q,u[MAXM+1],v[MAXM+1],l[MAXM+1],a[MAXM+1];

int dis[MAXN+1],beout[MAXN+1];

struct queue_data { int num,dis; };
struct cmp_queue { bool operator () (queue_data a,queue_data b) { return a.dis>b.dis; } };

void sortest_path () {
	priority_queue<queue_data,vector<queue_data>,cmp_queue> q;
	fill(dis+1,dis+n+1,1e9);
	fill(beout+1,beout+n+1,0);
	dis[1]=0; q.push((queue_data){1,0});
	queue_data now;
	while (!q.empty()) {
		now=q.top(); q.pop();
		if (beout[now.num]) continue;
		dis[now.num]=now.dis;
		beout[now.num]=1;
		for (int i=last[now.num];i;i=r[i].next)
		if (!beout[r[i].point])
			q.push((queue_data){r[i].point,dis[now.num]+r[i].value});
	} return;
}

int f[MAXN*2+1];

int getfather (int now) { return f[now]==now?now:f[now]=getfather(f[now]); }

int ft[MAXN*2+1][19],son[MAXN*2+1][2],value[MAXN*2+1],cost[MAXN*2+1],num;

void solve () {
	read_int(n),read_int(m);
	
	fill(last+1,last+n+1,0);
	tot=0;
	
	for (int i=1;i<=m;i++)
		read_int(u[i]),read_int(v[i]),
		read_int(l[i]),read_int(a[i]),
		link(u[i],v[i],l[i]),
		d[i]=(relation){u[i],v[i],a[i]};
	
	sortest_path();
	
	sort(d+1,d+m+1);
	for (int i=1;i<=n;i++)
		f[i]=i,cost[i]=dis[i],
		son[i][0]=son[i][1]=0;
	int x,y; num=n;
	for (int i=1;i<=m;i++) {
		x=getfather(d[i].u);
		y=getfather(d[i].v);
		if (x!=y) {
			ft[x][0]=ft[y][0]=++num;
			son[num][0]=x; son[num][1]=y;
			value[num]=d[i].value;
			f[x]=f[y]=f[num]=num;
			cost[num]=cost[x]<cost[y]?
				cost[x]:cost[y];
		}
	}
	
	const int maxp=log2(num);
	for (int p=1;p<=maxp;p++)
		for (int i=1;i<=num;i++)
			ft[i][p]=ft[ft[i][p-1]][p-1];
	
	int q,k,s,start,height,last_ans=0,now;
	
	read_int(q),read_int(k),read_int(s);
	while (q--) {
		read_int(start),read_int(height);
		start=(start+k*last_ans-1)%n+1;
		height=(height+k*last_ans)%(s+1);
		now=start;
		for (int i=maxp;i>=0;i--)
		if (ft[now][i]&&value[ft[now][i]]>height)
			now=ft[now][i];
		write_int(cost[now]);
		last_ans=cost[now];
	} return;
}

int main () {
	read_int(T);
	while (T--)
		solve();
	
	return 0;
}

评测结果