代码

#include<bits/stdc++.h>
using namespace std;
#define FE "return"
#define pb push_back
#define clr(a) memset(a,0,sizeof(a))
const int N=1000005,N2=N<<1,inf=0x3f3f3f3f;
int n,m,d[N2],mn[N2],vis[N],t,fa[N2][20],uf[N2],lust,Q,k,s;
struct node{int d,n;};
bool operator<(node a,node b){return b.d<a.d;}
priority_queue<node>q;
vector<int>e[N],f[N];
void dbg(string a,node x){cerr<<a<<"  ("<<x.d<<","<<x.n<<")\n";}
struct edge{int u,v,w,x;}ed[N2];
bool cmp(edge a,edge b){return b.x<a.x;}
void init();
int find(int a){if(uf[a])return uf[a]=find(uf[a]);return a;}
void build(){clr(fa),clr(uf),clr(mn);
    for(int i=1;i<=n;i++)mn[i]=inf;
    for(int i=0,j=n;i<m;i++){
        int v=find(ed[i].v),u=find(ed[i].u);
        if(v==u)continue;
        uf[v]=uf[u]=++j,fa[v][0]=fa[u][0]=j,d[j]=inf,mn[j]=ed[i].x;
    }n=(n<<1)-1;
    for(int i=1;i<=n;i++)
        d[fa[i][0]]=min(d[fa[i][0]],d[i]),mn[fa[i][0]]=min(mn[fa[i][0]],mn[i]);
    for(int k=1;k<20;k++)for(int i=1;i<=n;i++)fa[i][k]=fa[fa[i][k-1]][k-1];
    //for(int i=1;i<=n;i++)printf("%d %d %d\n",d[i],mn[i],fa[i][0]);
}
void solve(){lust=0;
    scanf("%d%d%d",&Q,&k,&s);
    while(Q--){
        int a,b;scanf("%d%d",&a,&b);
        a=(a+(long long)k*lust-1)%((n+1)>>1)+1,b=(b+(long long)k*lust)%(s+1);//printf("query %d %d\n",a,b);
        for(int k=19;~k;k--)if(b<mn[fa[a][k]])a=fa[a][k];
        printf("%d\n",lust=d[a]);
    }
}
int main(){
    freopen(FE".in","r",stdin);
    freopen(FE".out","w",stdout);
    scanf("%d",&t);while(t--){
        init();
        build();
        solve();
    }return 0;
}
void init(){clr(vis),clr(d);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)e[i].clear(),f[i].clear();
    for(int i=0;i<m;i++){
        int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
        e[a].pb(b),f[a].pb(c);
        e[b].pb(a),f[b].pb(c);
        ed[i]=(edge){a,b,c,d};
    }sort(ed,ed+m,cmp);
    for(int i=2;i<=n;i++)d[i]=inf;
    q.push((node){0,1});
    while(!q.empty()){
        node nod=q.top();q.pop();/[表情]g("out",nod);
        int v=nod.n;
        if(vis[v])continue;vis[v]=1;/[表情]g("ok",nod);
        for(int i=0;i<(int)e[v].size();i++){
            int u=e[v][i],w=d[v]+f[v][i];/[表情]g("chk",(node){w,u});
            if(!vis[u]&&w<d[u])d[u]=w,q.push((node){w,u});/[表情]g("in",(node){w,u});
        }
    }//for(int i=1;i<=n;i++){if(d[i]==inf)d[i]=2147483647;printf("%d ",d[i]);}
}

评测结果