代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define Rint register int
using namespace std;
const int MAXN = 400003, INF = 1000000007;
struct Edge {
    int u, v, high;
    inline bool operator < (const Edge &o) const {
        return high > o.high; 
    }
} e[MAXN];
int T, n, m, q, k, s, cnt, lastans, head[MAXN], to[MAXN << 1], nxt[MAXN << 1], len[MAXN << 1];
inline void add(int a, int b, int c){
    to[++ cnt] = b; len[cnt] = c; nxt[cnt] = head[a]; head[a] = cnt;
}
int dis[MAXN];
bool vis[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
inline void dijstra(){
    memset(vis, 0, sizeof vis);
    memset(dis, 0x7f, sizeof dis);
    dis[1] = 0;
    pq.push(make_pair(0, 1));
    while(!pq.empty()){
        pair<int, int> now = pq.top(); pq.pop();
        if(vis[now.second]) continue;
        vis[now.second] = true;
        for(Rint i = head[now.second];i;i = nxt[i])
            if(dis[to[i]] > dis[now.second] + len[i]){
                dis[to[i]] = dis[now.second] + len[i];
                pq.push(make_pair(dis[to[i]], to[i]));
            }
    }
}
int fa[MAXN];
inline int getf(int x){
    return x == fa[x] ? x : fa[x] = getf(fa[x]);
}
int cntx, headx[MAXN], tox[MAXN << 1], nxtx[MAXN << 1], dep[MAXN], p[MAXN], val[MAXN], f[20][MAXN];
inline void addx(int a, int b){
    tox[++ cntx] = b; nxtx[cntx] = headx[a]; headx[a] = cntx;
    tox[++ cntx] = a; nxtx[cntx] = headx[b]; headx[b] = cntx;
}
inline void dfs(int u){
    for(Rint i = 1;i <= 19;i ++) f[i][u] = f[i - 1][f[i - 1][u]];
    for(Rint i = headx[u];i;i = nxtx[i])
        if(tox[i] != f[0][u]){
            f[0][tox[i]] = u;
            dep[tox[i]] = dep[u] + 1;
            dfs(tox[i]);
            val[u] = min(val[u], val[tox[i]]);
        }
}
inline int query(int x, int y){
    for(Rint i = 19;~i;i --)
        if(dep[x] >= (1 << i) && p[f[i][x]] > y) x = f[i][x];
    return val[x];
}
inline void kruskal(){
    int cnt = n, tot = 0;
    for(Rint i = 1;i <= (n << 1);i ++) fa[i] = i;
    sort(e + 1, e + m + 1); 
    for(Rint i = 1;i <= m;i ++){
        int fa1 = getf(e[i].u), fa2 = getf(e[i].v);
        if(fa1 != fa2){
            addx(++ cnt, fa1); addx(cnt, fa2);
            fa[fa1] = fa[fa2] = fa[cnt] = cnt;
            p[cnt] = e[i].high;
            ++ tot;
        }
        if(tot == n - 1) break;
    }
    dfs(cnt);
}
int main(){
    scanf("%d", &T);
    while(T --){
        lastans = cnt = cntx = 0;
        memset(head, 0, sizeof head);
        memset(headx, 0, sizeof headx);
        scanf("%d%d", &n, &m);
        for(Rint i = 1;i <= m;i ++){
            int l;
            scanf("%d%d%d%d", &e[i].u, &e[i].v, &l, &e[i].high);
            add(e[i].u, e[i].v, l); add(e[i].v, e[i].u, l);
        }
        dijstra();
        for(Rint i = 1;i <= n;i ++) val[i] = dis[i];
        for(Rint i = n + 1;i <= (n << 1);i ++) val[i] = INF;
        scanf("%d%d%d", &q, &k, &s);
        kruskal();
        while(q --){
            int v, p;
            scanf("%d%d", &v, &p);
            v = (v + k * lastans - 1) % n + 1;
            p = (p + k * lastans) % (s + 1);
            printf("%d\n", lastans = query(v, p));
        }
    }
}

评测结果