代码

#include <bits/stdc++.h>
using namespace std;
int T,n,m;
#define SZ 999999
typedef pair<int,int> pii;
int val[SZ];
#define mp make_pair
#define fi first
#define se second
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
namespace DJ
{
int fst[SZ],vb[SZ],nxt[SZ],M=0,vc[SZ];
void ad_de(int a,int b,int c)
{++M; nxt[M]=fst[a]; fst[a]=M; vb[M]=b; vc[M]=c;}
void adde(int a,int b,int c)
{ad_de(a,b,c); ad_de(b,a,c);}
void go()
{
    for(int i=1;i<=n;++i) val[i]=2.01e9;
    val[1]=0; priority_queue<pii,vector<pii>,greater<pii> > pq;
    pq.push(mp(0,1));
    while(!pq.empty())
    {
        pii t=pq.top(); pq.pop();
        if(val[t.se]!=t.fi) continue;
        for esb(t.se,e,b)
        {
            if(val[b]<=t.fi+vc[e]) continue;
            val[b]=t.fi+vc[e]; pq.push(mp(val[b],b));
        }
    }
}
}
int fst[SZ],vb[SZ],nxt[SZ],M=0,ff[SZ];
void ad_de(int a,int b)
{++M; nxt[M]=fst[a]; fst[a]=M; vb[M]=b;}
struct edg {int u,v,l,a;} e[SZ];
bool operator < (edg a,edg b) {return a.a<b.a;}
int gf(int x) {return (ff[x]>=0)?gf(ff[x]):x;}
int dfn[SZ],rv[SZ],C=0; int fv[SZ];
void dfs(int x)
{
    dfn[x]=++C; rv[C]=x;
    for esb(x,e,b) dfs(b);
}
#define SS 16999999
int an=0,ch[SS][2]; pii cv[SS]; int hz[SZ];
void edt(int&x,int l,int r,int p,pii s)
{
    {int _=++an; ch[_][0]=ch[x][0]; ch[_][1]=ch[x][1]; x=_;}
    if(l==r) {cv[x]=s; return;}
    int m=(l+r)>>1;
    if(p<=m) edt(ch[x][0],l,m,p,s);
    else edt(ch[x][1],m+1,r,p,s);
}
const int Z=524288;
void sol()
{
    scanf("%d%d",&n,&m); M=DJ::M=C=0;
    for(int i=1;i<=n;++i) ff[i]=-1,fst[i]=DJ::fst[i]=0;
    for(int i=1;i<=m;++i)
        scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].l,&e[i].a),
        DJ::adde(e[i].u,e[i].v,e[i].l);
    sort(e+1,e+1+m); DJ::go();
    for(int i=m;i>=1;--i)
    {
        int a=gf(e[i].u),b=gf(e[i].v);
        if(a==b) continue;
        if((-ff[a])<(-ff[b])) swap(a,b);
        ff[a]+=ff[b]; ff[b]=a;
    }
    int ro=-1;
    for(int i=1;i<=n;++i)
        if(ff[i]>0) ad_de(ff[i],i); else ro=i;
    //cerr<<ro<<"\n";
    dfs(ro);
    /*
    for(int i=1;i<=n;++i)
        cerr<<val[i]<<",";
    cerr<<"\n";
    for(int i=1;i<=n;++i)
        cerr<<ff[i]<<",";
    cerr<<"\n";
    for(int i=1;i<=n;++i)
        cerr<<rv[i]<<",";
    cerr<<"\n";*/
    an=0;
    for(int i=1;i<=n;++i)
        ff[i]=-1,fv[i]=val[i],edt(hz[m+1],0,Z-1,dfn[i],pii(ff[i],fv[i]));
    for(int i=m;i>=1;--i)
    {
        int a=gf(e[i].u),b=gf(e[i].v); hz[i]=hz[i+1];
        if(a==b) continue;
        if((-ff[a])<(-ff[b])) swap(a,b);
        fv[a]=min(fv[a],fv[b]);
        ff[a]+=ff[b]; ff[b]=a;
        edt(hz[i],0,Z-1,dfn[a],pii(ff[a],fv[a]));
        edt(hz[i],0,Z-1,dfn[b],pii(ff[b],fv[b]));
    }
    int q,s,la=0; long long k;
    scanf("%d%lld%d",&q,&k,&s);
    for(int i=1;i<=q;++i)
    {
        int v,p;
        scanf("%d%d",&v,&p);
        v=(v+la*k-1)%n+1;
        p=(p+la*k)%(s+1);
        e[0].a=p;
        int g=upper_bound(e+1,e+1+m,e[0])-e,t=dfn[v];
        static int ss[100],ls[100],rs[100];
        int sn=0; ss[++sn]=hz[g]; ls[sn]=0; rs[sn]=Z-1;
        while(1)
        {
            while(t<ls[sn]||t>rs[sn]) --sn;
            while(ls[sn]!=rs[sn])
            {
                int m=(ls[sn]+rs[sn])>>1;
                if(t<=m) ++sn,ss[sn]=ch[ss[sn-1]][0],ls[sn]=ls[sn-1],rs[sn]=m;
                else ++sn,ss[sn]=ch[ss[sn-1]][1],ls[sn]=m+1,rs[sn]=rs[sn-1];
            }
            pii s=cv[ss[sn]];
            if(s.fi>0) {t=dfn[s.fi]; continue;}
            la=s.se; break;
        }
        printf("%d\n",la);
    }
}
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
int main()
{
    scanf("%d",&T);
    while(T--) sol();
}

评测结果