代码

#include<ctime>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define reg register
#define uni unsigned
using namespace std;
const uni N=400010,ISIZE=1<<26,OSIZE=1<<23,W=4,WT=4;
uni n,m,cnt,p[N],s[N],map[N],d[N<<2],w[N],up[N][23],mi[N],mx[N];
uni st[N],OnF;
uni seed=time(0);
struct edge{
    uni u,v,x,y;
}e[N];
struct CFS{
    uni a[N],last,b[N+N][3];
    void add(uni x,uni y,uni z){
        b[++last][0]=a[x];
        b[a[x]=last][1]=y;
        b[last][2]=z;
    }
}a,b;
char BuF[ISIZE],*InF=BuF,WuF[OSIZE];
uni read(){
    reg uni x=0;
    for(;47>*InF||*InF>58;++InF);
    for(;47<*InF&&*InF<58;x=x*10+(*InF++^48));
    return(x);
}
void write(uni x){
    if(!x){
        WuF[OnF++]=48;
    }
    for(;x;x/=10){
        st[++st[0]]=x%10+48;
    }
    for(;st[0];WuF[OnF++]=st[st[0]--]);
    WuF[OnF++]='\n';
}
bool cmp(edge a,edge b){
    return(a.y>b.y);
}
uni root(uni x){
    return(s[x]?s[x]=root(s[x]):x);
}
void kruskal(){
    sort(e,e+m,cmp);
    for(reg uni i=0,x,y;i<m;++i){
        if((x=root(e[i].u))!=(y=root(e[i].v))){
            p[s[x]=s[y]=++cnt]=e[i].y;
            b.add(cnt,x,0);
            b.add(cnt,y,0);
        }
    }
}
uni rnd(uni l,uni r){
    seed^=seed<<17;seed^=seed>>15;seed^=seed<<3;
    return(seed%(r-l+1)+l);
}
void change(reg uni &x,reg uni &y){
    swap(map[x],map[y]);
    swap(x,y);
}
void spfa(){
    memset(w,127,sizeof(w));
    w[d[0]=1]=0;
    for(reg uni h=0,t=0;h<=t;++h){
        reg uni *hd=d+h;
        if(h+W+W+3<t){
            for(reg uni i=0,l=h+W+2,r=t-W-1;i<=WT;++i){
                reg uni x=rnd(l,r);
                if(w[*hd]>w[d[x]]){
                    change(*hd,d[x]);
                }
            }
        }
        for(reg uni *i=d+h+1,*j=d+t,*r=d+h+W;i<r&&i<j;++i,--j){
            if(w[*hd]>w[*i]){
                change(*hd,*i);
            }
            if(w[*hd]>w[*j]){
                change(*hd,*j);
            }
        }
        for(reg uni tmp=*hd,i=a.a[tmp];i;i=a.b[i][0]){
            reg uni nxt=a.b[i][1],p=w[tmp]+a.b[i][2];
            if(w[nxt]>p){
                w[nxt]=p;
                if(map[nxt]){
                    if(w[nxt]<w[d[t]]){
                        change(d[map[nxt]],d[t]);
                    }
                }else{
                    d[map[nxt]=++t]=nxt;
                    if(t>h+1&&w[d[t-1]]<w[d[t]]){
                        change(d[t],d[t-1]);
                    }
                }
            }
        }
        map[*hd]=0;
    }
}
void dfs(uni x){
    for(reg uni &i=mx[x]=1;up[x][i-1];++i){
        up[x][i]=up[up[x][i-1]][i-1];
    }
    mi[x]=x>n?0x7fffffff:w[x];
    for(reg uni i=b.a[x];i;i=b.b[i][0]){
        up[b.b[i][1]][0]=x;
        dfs(b.b[i][1]);
        mi[x]=min(mi[x],mi[b.b[i][1]]);
    }
}
int main(){
    fread(BuF,1,ISIZE,stdin);
    for(uni T=read(),lastans=0;T;--T){
        n=read();m=read();
        cnt=n;
        lastans=a.last=b.last=0;
        memset(s,0,sizeof(s));
        memset(a.a,0,sizeof(a.a));
        memset(b.a,0,sizeof(b.a));
        for(reg uni i=0;i<m;++i){
            e[i].u=read();e[i].v=read();e[i].x=read();e[i].y=read();
            a.add(e[i].u,e[i].v,e[i].x);
            a.add(e[i].v,e[i].u,e[i].x);
        }
        kruskal();
        spfa();
        dfs(cnt);
        for(reg uni Q=read(),K=read(),S=read();Q;--Q){
            reg uni vi=read(),pi=read();
            if(K){
                vi=(vi+lastans-1)%n+1;
                pi=(pi+lastans)%(S+1);
            }
            for(reg uni i=mx[vi]-1;~i;--i){
                if(up[vi][i]&&p[up[vi][i]]>pi){
                    vi=up[vi][i];
                }
            }
            write(lastans=mi[vi]);
        }
    }
    fwrite(WuF,1,OnF,stdout);
    return(0);
}

评测结果