代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
 
using namespace std;
#define int long long
const int MAXN = 800800;
const int MAXM = 800800;
long long T, n, m, q, k, s, cnt, tot, fa[MAXN], dis[MAXN], h[MAXN], Min[MAXN], vis[MAXN], dp[MAXN][25];
long long Q[MAXN], hh, tt, flag[MAXN];
struct edge1 {
    long long v, w;
    edge1 *next;
}pool[MAXM ], *head[MAXN];
struct edge2 {
    int u, v, l;
    bool operator < (const edge2& _e) const {
        return l > _e.l;
    }
}e[MAXM];
struct node {
    int id, d;
    bool operator < (const node&x) const {
        return d > x.d;
    }
}tmp;
priority_queue <node> QQ;
inline void init() {
    cnt = 0; tot = n;
    memset(dis, 111, sizeof(dis));
    memset(Min, 111, sizeof(Min));
    memset(dp, 0, sizeof(dp));
    memset(h, 0, sizeof(h));
    memset(Q, 0, sizeof(Q));
    memset(vis, 0, sizeof(vis));
    memset(flag, 0, sizeof(flag));
    for(int i = 1; i <= MAXN; i++) 
        head[i] = NULL, fa[i] = i, e[i].u = e[i].v = e[i].l = 0;
}
inline void addedge(int u, int v, int w) {
    edge1 *p = &pool[++cnt], *q = &pool[++cnt];
    p->v = v, p->w = w, p->next = head[u], head[u] = p;
    q->v = u, q->w = w, q->next = head[v], head[v] = q;
}
inline int find(int x) {
    if(x == fa[x]) return x;
    else return fa[x] = find(fa[x]);
}
inline void spfa() {
    memset(flag, 0, sizeof(flag));
    hh = tt = 0;
    Q[++tt] = 1, dis[1] = 0; flag[1] = 1;
    while(hh <= tt) {
        int tmp = Q[hh++]; flag[tmp] = 0;
        for(edge1 *p = head[tmp]; p; p = p->next) {
            int v = p->v;
            if(dis[v] > dis[tmp] + p->w) {
                dis[v] = dis[tmp] + p->w;
                if(!flag[v]) Q[++tt] = v, flag[v] = 1;
            }
        }
    } 
}
inline void dijkstra()
{
    int u, v;
    dis[1] = 0, tmp.d = 0, tmp.id = 1, QQ.push(tmp);
    while(!QQ.empty())
    {
        tmp = QQ.top(); QQ.pop();
        if(dis[u = tmp.id] < tmp.d) continue;
        for(edge1 *p = head[u]; p; p = p->next)
            if(dis[v = (p->v)] > dis[u] + p->w)
            {
                dis[v] = dis[u] + p->w;
                tmp.id = v, tmp.d = dis[v], QQ.push(tmp);
            }
    }
}
inline void build_kruskal() {
    sort(e + 1, e + m + 1); tot = n;
    for(int i = 1; i <= MAXN; i++) head[i] = NULL; cnt = 0;
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= m; i++) {
        int x = find(e[i].u), y = find(e[i].v);
        if(x == y) continue;  
        h[++tot] = e[i].l;
        fa[x] = fa[y] = fa[tot] = tot;
        addedge(tot, x, 0), addedge(tot, y, 0);
    }
}
inline void dfs(int u) {
    Min[u] = dis[u]; vis[u] = 1;
    for(edge1 *p = head[u]; p; p = p->next) {
        int v = p->v;
        if(vis[v]) continue;
        vis[v] = 1; dp[v][0] = u;
        dfs(v); Min[u] = min(Min[u], Min[v]);
    }
}
#undef int
int main()
{
    scanf("%lld", &T);
    while(T--) {
        scanf("%d%d", &n, &m); init();
        for(int i = 1; i <= m; i++) {
            int u, v, w, l;
            scanf("%d%d%d%d", &u, &v, &w, &l);
            addedge(u, v, w);
            e[i].u = u, e[i].v = v, e[i].l = l; 
        }
        dijkstra();
        build_kruskal();
        dfs(tot);
        for(int i = 1; (1 << i) <= tot; i++)
            for(int j = 1; j <= tot; j++)
                dp[j][i] = dp[dp[j][i - 1]][i - 1];
        scanf("%lld%lld%lld", &q, &k, &s);
        long long last = 0;
        for(int i = 1; i <= q; i++) {
            long long v, p;
            scanf("%lld%lld", &v, &p);
            v = (v + k * last - 1) % n + 1;
            p = (p + k * last) % (s + 1);
            for(int j = 22; j >= 0; j--)
                if(dp[v][j] && h[dp[v][j]] > p)
                    v = dp[v][j];
            printf("%lld\n", last = Min[v]);
        }
    }
    return 0;
}

评测结果