代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 401000
#define INF 2147483647
using namespace std;
int n,m,las[N],to[N*4],nxt[N*4],date[N*4],S,K,ans=0,f[N],bz[N],tot=1,q,fa[N],g[N][19],h[N];
struct node{
	int x,y,u,v;
}b[N*2],edg[N*4];
struct note{
	int x,y;
	bool friend operator <(note a,note b){return a.y<b.y;}
};
multiset<note> s;
bool cnt(node a,node b){return a.y>b.y;}
void putin(int x,int y,int z)
{
	nxt[++tot]=las[x];las[x]=tot;to[tot]=y;date[tot]=z;
}
void SPFA()
{
	fo(i,1,n) f[i]=INF;
	f[1]=0;
	bz[1]=1;
	for(int i=las[1];i;i=nxt[i])
	{
		f[to[i]]=min(f[to[i]],f[1]+date[i]);
		note jy;
		jy.x=to[i];
		jy.y=f[to[i]];
		s.insert(jy);
	}
	fo(j,2,n)
	{
		note x=*s.begin();s.erase(s.begin());
		while(bz[x.x]) x=*s.begin(),s.erase(s.begin());
		bz[x.x]=1;
		for(int i=las[x.x];i;i=nxt[i])
		if(!bz[to[i]])
		{
			f[to[i]]=min(f[to[i]],f[x.x]+date[i]);
			note jy;
			jy.x=to[i];
			jy.y=f[to[i]];
			s.insert(jy);
		}
	}
}
void dg(int x)
{
	for(int i=las[x];i;i=nxt[i])
	{
		int y=to[i];
		g[y][0]=x;h[y]=date[i];
		dg(y);
	}
}
int gf(int x){return fa[x]==0?x:fa[x]=gf(fa[x]);}
int goup(int x,int y)
{
	fd(i,18,0) if(h[g[x][i]]>y) x=g[x][i];
	if(h[x]>y) x=g[x][0];
	return x;
}
int main()
{
	freopen("return5.in","r",stdin);
	freopen("return.out","w",stdout);
	int ac;scanf("%d",&ac);
	while(ac--)
	{
		scanf("%d%d",&n,&m);
		fo(i,1,n) fa[i]=0;
		fo(i,1,m)
		{
			int x,y,z,z1;scanf("%d%d%d%d",&x,&y,&z,&z1);
			putin(x,y,z);putin(y,x,z);
			edg[i].u=x;edg[i].v=y;edg[i].x=z;edg[i].y=z1;
		}
		sort(edg+1,edg+m+1,cnt);
		SPFA();
		memset(las,0,sizeof(las));tot=0;
		fo(i,1,m)
		{
			int x=edg[i].u,y=edg[i].v;
			x=gf(x),y=gf(y);
			if(x==y) continue;
			f[++n]=min(f[x],f[y]);
			fa[x]=n;fa[y]=n;
			putin(n,y,edg[i].y);
			putin(n,x,edg[i].y);
		}
		dg(n);
		fo(j,1,18) fo(i,1,n) g[i][j]=g[g[i][j-1]][j-1];
		scanf("%d%d%d",&q,&K,&S);
		while(q--)
		{
			int x,y;scanf("%d%d",&x,&y);
			x=(x-1+K*ans)%n+1;
			y=(y+K*ans)%(S+1);
			x=goup(x,y);
			printf("%d\n",f[x]);
		}
	}
}

评测结果