代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

const int MAXN = 800005;

int tot;
inline int newnode(){return ++tot;}

struct Undirected_Edge{
    int x,y,w;
    bool operator<(const Undirected_Edge &rhs)const {
        return w>rhs.w;
    }
}ue[MAXN];
struct Edge{
    int ecnt,head[MAXN],nxt[MAXN],to[MAXN],h[MAXN],l[MAXN];
    Edge(){ecnt=1;}
    void clear(){
        ecnt=1;
        memset(head,0,sizeof(head));    
    }
    void add(int x,int y,int _l=0,int _h=0){
        nxt[++ecnt] = head[x];
        to[ecnt] = y;
        h[ecnt] = _h;
        l[ecnt] = _l;
        head[x] = ecnt;
    }
}e,t;


int n,m;

struct Uno{
    int fa[MAXN];
    void init(int x){for(int i=1;i<=x;i++)fa[i]=i;}
    int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
    void cat(int x,int y){x=fnd(x);y=fnd(y);if(x==y)return;fa[x]=y;}
}U;
struct Node{
    int id,v;   
    Node(int _id=0,int _v=0){id=_id;v=_v;}
    bool operator <(const Node &rhs)const{return v>rhs.v;}
}top;
priority_queue<Node> Q;
int vis[MAXN],dis[MAXN];
void dij(){
    Q.push(Node(1,0));dis[1]=0;
    while(!Q.empty()){
        top=Q.top();Q.pop();    
        int mnid=top.id,mn=top.v;
        if(vis[mnid]||mn!=dis[mnid])continue;
        vis[mnid]=1;
        for(int i=e.head[mnid];i;i=e.nxt[i]){
            int v=e.to[i];
            if(dis[v]<=mn+e.l[i])continue;
            dis[v]=mn+e.l[i];
            Q.push(Node(v,dis[v])); 
        }
    }
}

int low[MAXN],val[MAXN],f[MAXN][32];
void init(){
    U.init(n<<1);tot=n;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(low,0x7f,sizeof(low));
    memset(val,0,sizeof(val));
    memset(f,0,sizeof(f));
    e.clear();t.clear();
}


void dfs(int x,int pre){
    f[x][0]=pre;low[x]=dis[x];
    for(int i=t.head[x];i;i=t.nxt[i]){
        int v=t.to[i];
        if(v==pre)continue;
        dfs(v,x);low[x]=min(low[x],low[v]);
    }
}

int q,k,s;
int lastans;

void solve(){
    lastans=0;//fff
    int x,y,u,v,l,h,cur;
    for(int i=1;i<=m;i++){
        x=rd();y=rd();l=rd();h=rd();
        e.add(x,y,l,h);e.add(y,x,l,h);
        ue[i].x = x;ue[i].y = y;ue[i].w = h;
    }
    dij();
    sort(ue+1,ue+1+m);
    int Edge_cnt=0;
    for(int i=1;i<=m;i++){
        x=ue[i].x,y=ue[i].y,h=ue[i].w;
        u=U.fnd(x);v=U.fnd(y);
        if(u==v)continue;
        cur=newnode();Edge_cnt++;
        U.cat(u,cur);U.cat(v,cur);
        t.add(u,cur);t.add(cur,u);
        t.add(v,cur);t.add(cur,v);
        val[cur]=h;
        if(Edge_cnt==n-1)break;   
    }
    int rt=U.fnd(1);
    dfs(rt,rt);
    for(int j=1;(1<<j)<=tot;j++){
        for(int i=1;i<=tot;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
    q=rd();k=rd();s=rd();
    for(int i=1;i<=q;i++){
        x=rd();y=rd();
        u=(x+k*lastans-1)%n+1;
        v=(y+k*lastans)%(s+1);
        for(int i=30;i>=0;i--){
            if(val[f[u][i]]<=v)continue;
            u=f[u][i];
        }
        printf("%d\n",low[u]);
        lastans=low[u];
    }
}

int T;

signed main(){
    T=rd();
    while(T--){
        n=rd();m=rd();
        init();
        solve();
    }
    return 0;
}

评测结果