代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

int n,m,T,q,x,y,z,zz,k,s,v0,p0,lastans,v,p,nowans;
const int N=1000000,INF=1e9;
int dis[N],vis[N],f[N],fa[N],ans[N],out[N];
struct link
{
	int top,fi[N],ne[N],la[N],to[N],l[N],h[N];
	inline void clear()
	{
		top=0,memset(fi,0,sizeof fi),memset(ne,0,sizeof ne),memset(la,0,sizeof la),memset(to,0,sizeof to),memset(l,0,sizeof l),memset(h,0,sizeof h);
	}
	inline void add(int x,int y,int z,int H)
	{
		top++,to[top]=y,l[top]=z,h[top]=H;
		if(fi[x]==0)fi[x]=top;else ne[la[x]]=top;
		la[x]=top;
	}
}L;
struct node
{
	int id,dis;
	bool operator < (const node &a) const {return a.dis < dis;}
};
priority_queue<node> que;
inline void DIJKSTRA()
{
    for(int i=1;i<=n;i++)dis[i]=INF,vis[i]=0;
    dis[1]=0;while(!que.empty())que.pop();
    node tmp;
    tmp.id=1;tmp.dis=0;que.push(tmp);
    while (!que.empty()) 
	{
        int now=que.top().id;
        que.pop();
        if (vis[now]) continue;
        vis[now]=true;
        for (int i=L.fi[now];i;i=L.ne[i]) 
		{
            if (!vis[L.to[i]]&&dis[L.to[i]]>dis[now]+L.l[i]) 
			{
                dis[L.to[i]]=dis[now]+L.l[i];
                tmp.id=L.to[i];tmp.dis=dis[L.to[i]];
                que.push(tmp);
            }
        }
    }
}
queue<int> Q;
inline void bfs(int s,int q)
{
	for(int i=1;i<=n;i++)vis[i]=0;vis[s]=1;Q.push(s);
	while(!Q.empty())
	{
		int now=Q.front();Q.pop();
		for(int i=L.fi[now];i;i=L.ne[i])
		if(!vis[L.to[i]]&&L.h[i]>q)vis[L.to[i]]=1,Q.push(L.to[i]);
	}
	for(int i=1;i<=n;i++)if(vis[i])nowans=min(nowans,dis[i]);
}
struct A{int v,q,id;}ask[N];
struct E{int x,y,l,h;}e[N];
inline bool cmp1(A a,A b){return a.q>b.q;}
inline bool cmp2(E a,E b){return a.h>b.h;}
inline int ASK(int x){if(fa[x]==x)return x;else return fa[x]=ASK(fa[x]);}
inline int Read()
{
    int x=0,f=1;char c=getchar();
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
    return x*f;
}
int main()
{
	
	T=Read();
	while(T--)
	{
		L.clear();lastans=0;n=Read(),m=Read();
		for(int i=1;i<=m;i++)
		{
			x=Read(),y=Read(),z=Read(),zz=Read();
			e[i].x=x,e[i].y=y,e[i].l=z,e[i].h=zz;
			L.add(x,y,z,zz),L.add(y,x,z,zz);
		}
		DIJKSTRA();
		q=Read(),k=Read(),s=Read();
		if(k==0)
		{
			for(int i=1;i<=n;i++)fa[i]=i,ans[i]=dis[i];
			for(int i=1;i<=q;i++)
			ask[i].v=Read(),ask[i].q=Read(),ask[i].id=i,ask[i].q%=(s+1);
			sort(e+1,e+1+m,cmp2),sort(ask+1,ask+1+q,cmp1);int now=1;
			for(int i=1;i<=q;i++)
			{
				while(e[now].h>ask[i].q&&now<=m)
				{
					int fx=ASK(e[now].x),fy=ASK(e[now].y);
					if(fx!=fy)
					{
						fa[fy]=fx;
						ans[fx]=ans[fy]=min(ans[fx],ans[fy]);
					}
					now++;
				}
				out[ask[i].id]=ans[ASK(ask[i].v)];
			}
			for(int i=1;i<=q;i++)printf("%d\n",out[i]);
		}else
		{
			for(int ttt=1;ttt<=q;ttt++)
			{
				v0=Read(),p0=Read();
				v=(v0+k*lastans-1)%n+1;
				p=(p0+k*lastans)%(s+1);
				nowans=INF;
				bfs(v,p);
				printf("%d\n",nowans);lastans=nowans;
			}
		}
		
	}
	return 0;
}

评测结果