代码

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
struct Edge{
	int u,v,l,val;
	Edge(){u=v=l=val=0;}
	Edge(int U,int V,int LON,int VAL){u=U,v=V,l=LON,val=VAL;}
	bool operator < (Edge another) const {return val>another.val;}
}ed[400005];
struct UnionFindSet{
	int fa[600005];
	void makeSet(int up){for(int i=0;i<=up;++i)	fa[i]=i;}
	int findSet(int x)
	{
		if(x==fa[x])	return x;
		return fa[x]=findSet(fa[x]);
	}
	void unionSet(int x,int y)
	{
		int xx=findSet(x),yy=findSet(y);
		if(xx==yy)	return ;
		fa[xx]=yy;
	}
	bool bunionSet(int x,int y)
	{
		int xx=findSet(x),yy=findSet(y);
		if(xx==yy)	return false;
		fa[xx]=yy;
		return true;
	}
}ufs;
struct node{
	int l,val;
}p[600005];
vector<int> G[600005];
vector<pair<int,int> > fc[600005];
int T,n,m,dis[600005],fa[600005][21],dep[600005];
void Dijkstra()
{
	for(int i=1;i<=2*n-1;++i)	dis[i]=1000000000;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;
	Q.push(mp(0,1));
	dis[1]=0;
	while(!Q.empty())
	{
		pair<int,int> tmp=Q.top();
		Q.pop();
		if(tmp.first>dis[tmp.second])	continue;
		int now=tmp.second,value=tmp.first;
		for(unsigned int i=0;i<fc[now].size();++i)
		{
			int to=fc[now][i].second,val=fc[now][i].first;
			if(value+val<dis[to])
			{
				dis[to]=value+val;
				Q.push(mp(value+val,to));
			}
		}
	}
	for(int i=1;i<=2*n-1;++i)	p[i].l=dis[i];
}
void Kruskal()
{
	ufs.makeSet(n*2-1);
	int now=n;
	sort(ed+1,ed+1+m);
	for(int i=1;i<=m;++i)
	{
		int u=ufs.findSet(ed[i].u),v=ufs.findSet(ed[i].v);
		if(u!=v)
		{
			ufs.fa[u]=ufs.fa[v]=++now;
			G[now].push_back(u);
			G[now].push_back(v);
			p[now].val=ed[i].val;
		}
	}
}
void dfs(int now,int pre)
{
	fa[now][0]=pre;
	dep[now]=dep[pre]+1;
	for(int i=1;i<=20;++i)	fa[now][i]=fa[fa[now][i-1]][i-1];
	for(unsigned int i=0;i<G[now].size();++i)
	{
		int to=G[now][i];
		dfs(to,now);
		p[now].l=min(p[now].l,p[to].l);
	}
}
int main(){
	p[0].l=2147483647;
	scanf("%d",&T);
	while(T-->0)
	{
//		memset(p,0,sizeof p);
//		memset(fa,0,sizeof fa);
//		memset(dep,0,sizeof dep);
//		memset(dis,0,sizeof dis);
		p[0].l=2147483647;
		scanf("%d %d",&n,&m);
		for(int i=1;i<=2*n;++i)	G[i].clear(),fc[i].clear();
		for(int i=1;i<=m;++i)
		{
			int u,v,l,val;
			scanf("%d %d %d %d",&u,&v,&l,&val);
			ed[i]=Edge(u,v,l,val);
			fc[u].push_back(mp(l,v));
			fc[v].push_back(mp(l,u));
		}
		Dijkstra();
		Kruskal();
		dfs(2*n-1,0);
		int q,K,S,lastans=0;
		scanf("%d %d %d",&q,&K,&S);
		while(q-->0)
		{
			int v,s;
			scanf("%d %d",&v,&s);
			v=(v+K*lastans-1)%n+1;
			s=(s+K*lastans)%(S+1);
			int now=v;
			for(int i=20;~i;--i)	if(p[fa[now][i]].val>s)	now=fa[now][i];
			printf("%d\n",lastans=p[now].l);
		}
	}
	return 0;
}

评测结果