代码

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
    char c=getchar();
    int p=1;
    x=0;
    while(!isdigit(c)){
        if(c=='-')p=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    x*=p;
}
const int maxn = 800050;
#define pa pair<int, int>
#define mp make_pair
struct edge{
    int to, next;
    long long w;
}e[maxn << 1];
struct edge1{
    int u, v, a;
}e1[maxn << 1];
priority_queue<pa > qu;
inline bool cmp(edge1 a, edge1 b){
    return a.a > b.a;
}
int head[maxn], f[maxn], n, m, cnt, tot, top[maxn][23];
long long mi[maxn], val[maxn], dis[maxn];
bool vis[maxn];
inline void add(int u, int v, long long w){
    e[++tot].to = v;
    e[tot].next = head[u];
    e[tot].w = w;
    head[u] = tot;
}
inline void dijkstra(){
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    qu.push(mp(0, 1));
    while(!qu.empty()){
        int u = qu.top().second;
        qu.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(register int i = head[u]; i; i = e[i].next){
            int v = e[i].to;
            if(dis[u] + e[i].w < dis[v]){
                dis[v] = dis[u] +e[i].w;
                qu.push(mp(-dis[v], v));
            }
        }
    }
}
inline int getf(int u){
    return f[u] == u ? f[u] : f[u] = getf(f[u]);
}
inline void pre(){
    memset(head, 0, sizeof(head));
    tot = 1;
    for(register int i = 0; i <= n + 1; ++i){
        f[i] = i;
    }
}
inline void init(){
    memset(head, 0, sizeof(head));
    tot = 1;
    cnt = n;
    memset(mi, 0x3f, sizeof(mi));
    memset(top, 0, sizeof(top));
}
inline void dfs(int u, int fa){
    top[u][0] = fa;
    mi[u] = dis[u];
    for(register int i = head[u]; i; i = e[i].next){
        int v = e[i].to;
        if(v == fa)return ;
        dfs(v, u);
        mi[u] = min(mi[u], mi[v]);
    }
}
inline void build_kruskal(){
    pre();
    for(register int i = 1; i <= m; ++i){
        int fu = getf(e1[i].u), fv = getf(e1[i].v);
        if(fu != fv){
            val[++cnt] = e1[i].a;
            f[fu] = f[fv] = f[cnt] = cnt;
            add(cnt, fu, 0), add(cnt, fv, 0);
        }
    }
    dfs(cnt, 0);
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int T;
    read(T);
    while(T--){
        read(n), read(m);
        init();
        int u, v, a, p;
        long long w;
        for(register int i = 1; i <= m; ++i){
            read(u), read(v), scanf("%lld", &w), read(a);
            add(u, v, w), add(v, u, w);
            e1[i].u = u, e1[i].v = v, e1[i].a = a;
        }
        sort(e1 + 1, e1 + 1 + m, cmp);
        dijkstra();
        build_kruskal();
        for(register int i = 1; (1 << i) <= cnt; ++i){
            for(register int j = 1; j <= cnt; ++j){
                top[j][i] = top[top[j][i - 1]][i - 1];
            }
        }
        int q, k, s;
        read(q), read(k), read(s);
        long long lst = 0;
        while(q--){
            read(v), read(p);
            v = (v + k * lst - 1) % n + 1;
            p = (p + k * lst) % (s + 1);
            for(register int i = 22; i >= 0; --i){
                if(top[v][i] && val[top[v][i]] > p){
                    v = top[v][i];
                }
            }
            //cout<<v<<endl;
            //cout<<dis[3]<<":::"<<endl;
            printf("%lld\n", lst = mi[v]);
        }
    }
    return 0;
}

评测结果