代码

#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define low_b lower_bound
#define upp_b upper_bound
template <class Vec_T>
using vc=vector<Vec_T>;
const long long INF=(long long)(1e18);

struct edge{
    long long u, v, l, a;
    bool operator<(const edge &b) const{
        return a > b.a;
    }
    bool operator>(const edge &b) const{
        return l > b.l;
    }
};
struct node{
    long long ls, rs, fa, val;
};
long long f[200005];
void init(long long n){
    for(long long i=1;i <= n;i++) f[i]=i;
}
long long find(long long x){
    if(x == f[x]) return x;
    else return f[x]=find(f[x]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    long long T;
    cin >> T;
    while(T--){
        long long n, m;
        cin >> n >> m;
        vc<vc<edge>> adj(n+5);
        vc<edge> e;
        for(long long i=1;i <= m;i++){
            long long u, v, l, a;
            cin >> u >> v >> l >> a;
            adj[u].push_back({0, v, l, a});
            adj[v].push_back({0, u, l, a});
            e.push_back({u, v, l, a});
        }
        vc<long long> dis(n+5, INF);
        auto dj=[&](){
            priority_queue<edge, vc<edge>, greater<edge>> pq;
            pq.push({0, 1, 0, 0});
            dis[1]=0;
            vc<bool> vis(n+5);
            while(!pq.empty()){
                long long u=pq.top().v;
                pq.pop();
                // cerr << u << "\n";
                if(vis[u]) continue;
                vis[u]=1;
                for(auto v : adj[u]){
                    if(dis[u]+v.l < dis[v.v]){
                        dis[v.v]=dis[u]+v.l;
                        pq.push({0, v.v, dis[v.v], 0});
                    }
                }
            }
        };
        dj();
        // for(long long i=1;i <= n;i++){
        //     cout << dis[i] << " ";
        // }
        // cout << "\n";
        sort(e.begin(), e.end());
        long long tot=n;
        init(2*n);
        fill(adj.begin(), adj.end(), vc<edge>(0));
        vc<node> t(2*n+5);
        for(auto x : e){
            if(find(x.u) != find(x.v)){
                x.u=find(x.u);
                x.v=find(x.v);
                f[x.u]=++tot;
                f[x.v]=tot;
                t[tot]={x.u, x.v, 0, x.a};
                t[x.u].fa=t[x.v].fa=tot;
            }
        }
        // for(long long i=1;i <= tot;i++){
        //     cout << i << " " << t[i].ls << " " << t[i].rs << " " << t[i].val << "\n";
        // }
        vc<long long> mi(tot+5);
        vc<vc<long long>> f(tot+5, vc<long long>(21));
        auto dfs=[&](auto&& dfs, long long u)->void
        {
            f[u][0]=t[u].fa;
            if(t[u].ls == 0){
                mi[u]=dis[u];
                return;
            }
            dfs(dfs, t[u].ls);
            dfs(dfs, t[u].rs);
            mi[u]=min(mi[t[u].ls], mi[t[u].rs]);
        };
        dfs(dfs, tot);
        // for(long long i=1;i <= tot;i++){
        //     cerr << i << " " << f[i][0] << "\n";
        // }
        for(long long j=1;j <= 20;j++){
            for(long long i=1;i <= tot;i++){
                f[i][j]=f[f[i][j-1]][j-1];
            }
        }
        auto jump=[&](long long u, long long lim){
            for(long long i=20;i >= 0;i--){
                if(f[u][i] != 0 && t[f[u][i]].val > lim){
                    u=f[u][i];
                }
            }
            return mi[u];
        };
        long long q, K, S, lastans=0;
        cin >> q >> K >> S;
        for(long long i=1;i <= q;i++){
            long long v0, p0;
            cin >> v0 >> p0;
            long long v=(v0+K*lastans-1)%n+1, p=(p0+K*lastans)%(S+1);
            // cerr << v << " " << p << "p\n";
            cout << (lastans=jump(v, p)) << "\n";
        }
        return 0;
    }
    return 0;
}

评测结果