代码

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define Maxn	400050
#define LL  	long long
using namespace std;
template <typename tn> void read(tn &a){
    tn x = 0, f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    a = x * f;
}

struct node{ int u, v, a; } E[Maxn * 4];
LL dis[Maxn], lst_ans;
int n, m, Q, K, C;

bool cmp(node p, node q){ return p.a > q.a; }

namespace Dijkstra{
    struct node{ int u; LL d; };
    bool operator > (node p, node q){ return p.d > q.d; }
    priority_queue <node, vector<node>, greater<node> > que;
    struct Edge{ int v, l, next; } edge[Maxn * 10];
    int first[Maxn], Top;
    void addedge(int u, int v, int l, int f){
        edge[++Top] = (Edge) {v, l, first[u]}, first[u] = Top;
        if (f > 1) addedge(v, u, l, f - 1);
    }
    void clear(){ memset(first, 0, sizeof first), Top = 0; }
    void solve(){
        memset(dis, -1, sizeof dis); dis[1] = 0;
        while (que.size()) que.pop(); que.push((node) {1, 0});
        while (que.size()){
            int u = que.top().u; LL d = que.top().d; que.pop();
            if (d > dis[u]) continue;
            for (int i = first[u]; i; i = edge[i].next){
                int v = edge[i].v, l = edge[i].l;
                if (dis[v] == -1 || d + l < dis[v])
                    dis[v] = d + l, que.push((node) {v, d + l});
            }
        }
    }
};

struct Chairman_tree{

    #define N   	17500000
    struct info{ int fa, dep; LL dis; } tr[N];
    int rt[Maxn * 2], lc[N], rc[N], cnt;
    
    void clear(){ 
        memset(rt, 0, sizeof rt), cnt = 0;
        memset(lc, 0, sizeof lc);
        memset(rc, 0, sizeof rc);
    }
    void build(int &pos, int l, int r){
        pos = ++cnt;
        if (l == r){ tr[pos] = (info) {l, 1, dis[l]}; return; }
        int mid = (l + r) >> 1;
        build(lc[pos], l, mid), build(rc[pos], mid + 1, r);
    }
    void update(int old, int &pos, int P, info x, int l, int r){
        pos = ++cnt;
        lc[pos] = lc[old], rc[pos] = rc[old], tr[pos] = tr[old];
        if (l == r){ tr[pos] = x; return; }
        int mid = (l + r) >> 1;
        if (P <= mid) update(lc[old], lc[pos], P, x, l, mid);
        else update(rc[old], rc[pos], P, x, mid + 1, r);
    }
    void update(int id, int P, info x){ 
        int tmp = rt[id];
        update(tmp ? tmp : rt[id - 1], rt[id], P, x, 1, n); 
    }
    info query(int pos, int P, int l, int r){
        if (l == r) return tr[pos];
        int mid = (l + r) >> 1;
        return P <= mid ? query(lc[pos], P, l, mid) : query(rc[pos], P, mid + 1, r);
    }
    info query(int id, int P){ return query(rt[id], P, 1, n); }
    info getfa(int id, int x){
        info ret = query(id, x);
        for (; ret.fa != x; x = ret.fa, ret = query(id, x));
        return ret;
    }
    void merge(int id, int x, int y){
        info fx = getfa(id - 1, x), fy = getfa(id - 1, y), nx, ny;
        if (fx.fa == fy.fa){ rt[id] = rt[id - 1]; return; }
        if (fx.dep < fy.dep) swap(fx, fy);
        ny = fy; ny.fa = fx.fa, update(id, fy.fa, ny);
        nx.fa = fx.fa, nx.dep = fx.dep + (fx.dep == fy.dep), nx.dis = min(fx.dis, fy.dis);
        if (nx.dis != fx.dis || nx.dep != fx.dep) update(id, fx.fa, nx);
    }
    LL gdis(int id, int x){ return getfa(id, x).dis; }

} S;

void init(){
    Dijkstra :: clear();
    S.clear();
}
int find(int x){
    int lft = 1, rgt = m, ans = 0;
    while (lft <= rgt){
        int mid = (lft + rgt) >> 1;
        if (E[mid].a <= x) rgt = mid - 1;
        else lft = mid + 1, ans = mid;
    }
    return ans;
}

int main(){
    int T; read(T);
    while (T--){
        init();
        read(n), read(m);
        for (int i = 1, u, v, l, a; i <= m; i++){
            read(u), read(v), read(l), read(a);
            Dijkstra :: addedge(u, v, l, 2);
            E[i] = (node) {u, v, a};
        }
        sort(E + 1, E + m + 1, cmp);
        Dijkstra :: solve(); S.build(S.rt[0], 1, n);
        for (int i = 1; i <= m; i++){
            int u = E[i].u, v = E[i].v;
            S.merge(i, u, v);
        }
        read(Q), read(K), read(C), lst_ans = 0;
        for (int i = 1; i <= Q; i++){
            LL u, p; read(u), read(p);
            u = (u + K * lst_ans - 1) % n + 1;
            p = (p + K * lst_ans) % (C + 1);
            cout << (lst_ans = S.gdis(find(p), u)) << '\n';
        }
    }
    return 0; 
}

评测结果