代码

#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define M 400010
#define ll long long
/*inline int read(){
    char ch=getchar(); int x=0,f=1;
    for (;ch>'9'||ch<'0';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*f;
}*/
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    char ch=nc(); int x=0,f=1;
    for (;ch>'9'||ch<'0';ch=nc()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=nc()) x=x*10+ch-'0';
    return x*f;
}
struct Edge{
    int u,v,l,a;
    void gett(){
        u=read(),v=read(),l=read(),a=read();
    }
    bool operator<(const Edge&p) const{
        return a>p.a;
    }
}E[M];
struct node{
    int d,x;  
    node(){}
    node(int d,int x):d(d),x(x){};
    bool operator<(const node& b)const {
        return d>b.d;
    }  
};
struct segment{
    int l,r,dep,bel;
    ll Min;
}T[N*100];
int he[N],ne[M<<1],e[M<<1],va[M<<1],cnt,sz,rt[M],n,m;
ll dis[N];
bool vis[N];
void dij(int S){
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[S]=0; 
    priority_queue<node>Q;
    Q.push(node(0,S));
    while (!Q.empty()){
        int x=Q.top().x; Q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        for (int i=he[x];i;i=ne[i])
            if (dis[e[i]]==-1 || dis[e[i]]>dis[x]+va[i]){
                dis[e[i]]=dis[x]+va[i];
                Q.push(node(dis[e[i]],e[i]));
            }
    }
}
void build(int &t,int l,int r){
    t=++sz; 
    if (l==r){
        T[t].l=T[t].r=0;
        T[t].bel=l;
        T[t].Min=dis[l];
        return;
    }
    int mid=l+r>>1;
    build(T[t].l,l,mid); build(T[t].r,mid+1,r);
}
void modify(int l,int r,int x,int &y,int pos,int val){//鎶妏os骞跺埌val涓?
    y=++sz;
    if (l==r){
        T[y].bel=val;
        T[y].dep=T[x].dep;
        return;
    }
    T[y].l=T[x].l; T[y].r=T[x].r; int mid=l+r>>1;
    if (pos<=mid) modify(l,mid,T[x].l,T[y].l,pos,val);
    else modify(mid+1,r,T[x].r,T[y].r,pos,val);
}
void modify2(int &t,int pre,int l,int r,int pos,ll val){
	t=++sz; T[t]=T[pre];
    if (l==r){T[t].Min=min(T[t].Min,val);return;}
    int mid=l+r>>1;
    if (pos<=mid) modify2(T[t].l,T[pre].l,l,mid,pos,val);
    else modify2(T[t].r,T[pre].r,mid+1,r,pos,val);
}
void add(int t,int l,int r,int pos){
    if (l==r){T[t].dep++; return;}
    int mid=l+r>>1;
    if (pos<=mid) add(T[t].l,l,mid,pos);
    else add(T[t].r,mid+1,r,pos);
}
void add(int u,int v,int w){
    ne[++cnt]=he[u];he[u]=cnt;e[cnt]=v; va[cnt]=w;
}
int erfen(int p,int l,int r){
    int res=0;
    while (l<=r){
        int mid=l+r>>1;
        if (E[mid].a>p){res=mid; l=mid+1;}
        else r=mid-1;
    }
    return res;
}
int query(int t,int l,int r,int x){
    if (l==r) return t;
    int mid=l+r>>1;
    if (x<=mid) return query(T[t].l,l,mid,x);
    else return query(T[t].r,mid+1,r,x);
}
int find(int t,int x){
    int p=query(t,1,n,x);
    if (x==T[p].bel) return p;
    return find(t,T[p].bel);
}
int main(){

    int TT=read();
    while (TT--){
        n=read(),m=read();
        E[0].a=2e9; sz=0; cnt=0;
        memset(he,0,sizeof(he)); 
        for (int i=1;i<=m;i++){
            E[i].gett();
            add(E[i].u,E[i].v,E[i].l);
            add(E[i].v,E[i].u,E[i].l);
        }
        dij(1);
    //    for (int i=1;i<=n;i++) printf("%d ",dis[i]); puts("");
        sort(E+1,E+1+m); 
        build(rt[0],1,n);
        for (int i=1;i<=m;i++){
            rt[i]=rt[i-1]; int x=E[i].u,y=E[i].v;
            int p=find(rt[i],x),q=find(rt[i],y);
            if (T[p].bel==T[q].bel) continue;
            if (T[p].dep>T[q].dep) swap(p,q);
            modify(1,n,rt[i-1],rt[i],T[p].bel,T[q].bel);
            modify2(rt[i],rt[i],1,n,T[q].bel,T[p].Min);
            if (T[p].dep==T[q].dep) add(rt[i],1,n,T[q].bel);
        //    printf("rt[%d]::",i);for (int j=1;j<=n;j++) printf("%d ",T[find(rt[i],j)].bel); puts("");
        //   printf("MIN[%d]::",i);for (int j=1;j<=n;j++) printf("%d ",T[find(rt[i],j)].Min); puts("");
        //    printf("AAA%d\n",T[find(rt[1],2)].Min);
        //    printf("BBB%d\n",find(rt[1],2));

        }
        int Q=read(),K=read(),S=read(); ll la=0;
        while (Q--){
            int v=read(),p=read();
            v=(v+K*la-1)%n+1; p=(p+K*la)%(S+1);
            int pp=erfen(p,0,m);
        //    printf("[]%d %d\n",p,pp);
            int t=find(rt[pp],v);
        //    printf("::%d %d %d\n",t,T[t].bel,T[t].Min);
            printf("%lld\n",la=T[find(rt[pp],v)].Min);
        }
    }
  //  while (1);
    return 0;
}

评测结果