代码

#define ri register int
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=400005;
inline int re(){
    ri x=0,w=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}
int T,n,m,lastans,cnt,tot,q,k,s;
int last[N],dis[N],fa[N],f[N][25],H[N];
bool vis[N];
struct node{int id,d;};
struct Edge{int u,v,h;}E[N];
struct edge{int to,next,w;}e[N<<1];
bool operator <(node a,node b){return a.d>b.d;}
inline void link(ri u,ri v,ri w){
    e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
    e[++cnt]=(edge){u,last[v],w};last[v]=cnt;
}
inline bool cmp(Edge a,Edge b){return a.h>b.h;}
priority_queue<node>Q;
inline void Dij(){
    memset(dis,63,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;Q.push((node){1,0});
    while(!Q.empty()){
        ri u=Q.top().id;Q.pop();
        if(vis[u])continue;vis[u]=1;
        for(ri i=last[u],v;i;i=e[i].next){
            v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                Q.push((node){v,dis[v]});
            }
        }
    }
}
int find(ri x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void Kru(){
    tot=n;
    memset(f,0,sizeof(f));
    memset(H,0,sizeof(H));
    for(ri i=1;i<(n<<1);i++)fa[i]=i;
    sort(E+1,E+m+1,cmp);
    for(ri i=1,x,y;i<=m;i++){
        x=find(E[i].u);
        y=find(E[i].v);
        if(x==y)continue;
        fa[x]=fa[y]=f[x][0]=f[y][0]=++tot;
        H[tot]=E[i].h;
        dis[tot]=min(dis[x],dis[y]);
    }
    for(ri j=1;j<=20;j++)
        for(ri i=1;i<=tot;i++)
            f[i][j]=f[f[i][j-1]][j-1];
}
inline int Query(ri x,ri h){
    for(ri i=20;i>=0;i--)
        if(f[x][i]&&H[f[x][i]]>h)
            x=f[x][i];
    return dis[x];
}
int main(){
    T=re();
    while(T--){
        lastans=0;cnt=0;
        n=re(),m=re();
        memset(last,0,sizeof(last));
        for(ri i=1,u,v,l,a;i<=m;i++){
            u=re(),v=re(),l=re(),a=re();
            E[i]=(Edge){u,v,a};
            link(u,v,l);
        }
        Dij();
        Kru();
        q=re(),k=re(),s=re();
        ri v,p;
        while(q--){
            v=(re()+k*lastans-1)%n+1;
            p=(re()+k*lastans)%(s+1);
            printf("%d\n",lastans=Query(v,p));
        }
    }
    return 0;
}

评测结果