代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 3;
const int INF = 2e9 + 7;
struct edge{
    int to;
    int from;
    int nxt;
    int si;
    int li; 
}e[N << 1];
int head[N];LL dis[N];
int S[N];
int f[21][N];
vector <int> G[N];
int minn[N];
priority_queue <pii,vector<pii>,greater<pii> > q;
int n,m,tot,cnt;
int Q,kk,SS;
int fa[N];
inline void djh(int s){
    memset(dis,0x7f,sizeof(dis));
    dis[s] = 0; 
    q.push(mk(dis[s],s));
    while(!q.empty()){
        pii k = q.top();q.pop();
        if(k.fi != dis[k.se]) continue;
        for(int i = head[k.se];i;i = e[i].nxt){
            int y = e[i].to;
            if(dis[y] > dis[k.se] + e[i].li){
                dis[y] = dis[k.se] + e[i].li;
                q.push(mk(dis[y],y));
            }
        }
    }
}
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
inline void add(int x,int y,int z1,int z2){
    e[++tot].from = x;
    e[tot].to = y;
    e[tot].li = z1;
    e[tot].si = z2;
	e[tot].nxt = head[x];
    head[x] = tot;  
    e[tot + m].from = y;
    e[tot + m].to = x;
    e[tot + m].li = z1;
    e[tot + m].si = z2;
    e[tot + m].nxt = head[y];
    head[y] = tot + m;
}
inline bool cmp(edge x,edge y){
    return x.si > y.si;
}   
inline void dfs(int x){
//	printf("%d\n",x);
    minn[x] = dis[x];
    for(int i = 0;i < (int)G[x].size();++i){
        int y = G[x][i];
        f[0][y] = x;
        dfs(y);
        minn[x] = min(minn[x],minn[y]);
    }
}
inline int getf(int x){
	return fa[x] == x ? x : fa[x] = getf(fa[x]);	
}
int main(){
    int T = read();
    while(T--){
        n = read(),m = read();cnt = n;
        tot = 0;
        memset(head,0,sizeof(head));
        memset(f,0,sizeof(f));
        memset(minn,0x7f,sizeof(minn));
        memset(S,0,sizeof(S));
        for(int i = 1;i <= 2 * n;++i) fa[i] = i,G[i].clear();
        for(int i = 1;i <= m;++i){
            int x = read(),y = read(),w1 = read(),w2 = read();
            add(x,y,w1,w2);
        }
        djh(1);
        sort(e + 1,e + tot + 1,cmp);
        for(int i = 1;i <= tot;++i){
            int x = getf(e[i].from),y = getf(e[i].to);
            if(x == y) continue;
          //  printf("%d %d %d %d %d\n",e[i].from,e[i].to,x,y,cnt + 1); 
            ++cnt;
            fa[x] = cnt;fa[y] = cnt;
            G[cnt].push_back(x),G[cnt].push_back(y);
            S[cnt] = e[i].si;
        }
        dfs(getf(1));
       // for(int i = 1;i <= n + n - 1;++i) printf("%d ",S[i]);
        for(int j = 1;j <= 19;++j)
            for(int i = 1;i <= n + n - 1;++i)   
                f[j][i] = f[j - 1][f[j - 1][i]];
        Q = read(),kk = read(),SS = read();
        int lastans = 0;
        while(Q--){
            int x = (read() + 1ll * kk * lastans - 1) % n + 1,p = (read() + 1ll * kk * lastans) % (SS + 1);
            
            for(int i = 19;i >= 0;--i)
            if(f[i][x] != 0 && S[f[i][x]] > p) x = f[i][x];//printf("%d %d\n",x,p);
            printf("%d\n",lastans = minn[x]);
        }
    }
    return 0;
}

评测结果