代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long 
#define mp make_pair
using namespace std;
typedef pair<int,int> pa;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-') w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();} return w*s;}
int fa[1000010],cnt,rt,h[1000010],tot,tot1,h2[1000010],size[1000100],val[1000001];
ll dis[1000100];
struct node{
    int u,v,w,H;
}e[1000010];
struct edge 
{
    int to,next,w;
}E[1000100],E1[1000010];
int n,m,ANS;
int find(int k){if(fa[k]==k) return k;else return fa[k]=find(fa[k]);}
int anc[1000010][20];
int vis[1000100];
int query(int x,int y) {
    for(register int i=19;i>=0;--i) if(val[anc[x][i]]>y) x=anc[x][i];
    return dis[x];
}
inline void add1(int from,int to,int w){
    E[++tot].to=to;E[tot].next=h[from];E[tot].w=w;h[from]=tot;
}
inline void add2(int from,int  to){
    E1[++tot1].to=to;E1[tot1].next=h2[from];h2[from]=tot1;
}
inline bool cmp(node p,node q){return p.H>q.H;}
void DFS(int now,int ffa)
{
    vis[now]=1;
    for(register int i=h2[now];i;i=E1[i].next)
    {	int to=E1[i].to;if(to==ffa) continue;if(vis[to]) continue;DFS(to,now);
        dis[now]=min(dis[now],dis[to]);
    }
}
inline void dij(int s)
{
    priority_queue<pa, vector<pa>, greater<pa> > que; 
    que.push(mp(0,s));memset(dis,0x3f,sizeof(dis));dis[s]=0;
    while(!que.empty())
    {
        pa tmp=que.top();que.pop();
        int u=tmp.second;if(dis[u]!=tmp.first) continue;
        for(register int i=h[u];i;i=E[i].next)
        {	int to=E[i].to;
            if(dis[to]>dis[u]+E[i].w){
                dis[to]=dis[u]+E[i].w;que.push(mp(dis[to],to));
            }
        }
    }
}
inline void build_st(){for(register int i=1;i<=19;++i) for(register int j=1;j<=cnt;++j) anc[j][i]=anc[anc[j][i-1]][i-1];}
inline void solve(){
    val[0]=-1e9;
    for(register int i=1,u,v,w,H;i<=m;++i) u=read(),v=read(),w=read(),H=read(),e[i].u=u,e[i].v=v,e[i].w=w,e[i].H=H,add1(u,v,w),add1(v,u,w);
    for(register int i=1;i<=n;++i) fa[i]=i,size[i]=1;
    sort(e+1,e+m+1,cmp);cnt=n;
    for(register int i=1;i<=m;++i)
    {
        int u=e[i].u,v=e[i].v;u=find(u);v=find(v);
        if(u!=v)
        {
            ++cnt;
            fa[u]=cnt;fa[v]=cnt;val[cnt]=e[i].H;add2(u,cnt);add2(v,cnt);add2(cnt,v);add2(cnt,u);
            anc[u][0]=cnt,anc[v][0]=cnt;fa[cnt]=cnt;
        }
    }dij(1);DFS(find(1),0);build_st();int q=read(),k=read(),s=read();
    for(register int i=1;i<=q;++i)
    {
        ll u=read(),H=read();u=(u+1ll*k*ANS-1)%n+1;H=(H+1ll*k*ANS)%(s+1);
        cout<<(ANS=query(u,H))<<"\n";
    }
}
inline void init()
{
	ANS=0;
}
int main()
{
    int t=read();
    while(t--)
    {
        tot=0;memset(h,0,sizeof(h));tot1=0;memset(h2,0,sizeof(h2));memset(vis,0,sizeof(vis));
        init(); 
        n=read(),m=read();
        solve();
    }
    return 0;
}

评测结果