代码

#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
#define mkpr make_pair
#define ft first
#define sd second

typedef long long LL;
typedef pair<int, int> PII;
const int MAXN=400011, MAXM=800011;
struct edge {
    int x, y, l, h, nxt;
} OE[MAXN<<1], E[MAXM<<1];
int ohead[MAXN], head[MAXN], vis[MAXN], fa[MAXN], idx[MAXN], nh[MAXN], anc[MAXN][21], eid[MAXM];
LL dis[MAXN], mnd[MAXN];
int n, m, q, top, k, s, tot;
priority_queue<PII, vector<PII>, greater<PII> > Q;

inline bool cmp(int a, int b) {
    return OE[a].h!=OE[b].h ? OE[a].h>OE[b].h : OE[a].x<OE[b].x;
}

inline int getfa(int x) {
    return fa[x]==x ? x : fa[x]=getfa(fa[x]);
}

inline void addoedge(int x, int y, int l, int h) {
    OE[++tot]=(edge){x, y, l, h, ohead[x]};
    ohead[x]=tot;
}

inline void addedge(int x, int y, int l, int h) {
    // printf("%d <-> %d : %d %d\n", x, y, l, h);
    E[++tot]=(edge){x, y, l, h, head[x]};
    head[x]=tot;
}

inline void Dijkstra() {
    memset(dis, 0x7f, sizeof dis);
    memset(vis, 0, sizeof vis);
    while(!Q.empty()) Q.pop();
    Q.push(mkpr(0, 1));
    dis[1]=0;
    while(!Q.empty()) {
        PII now=Q.top(); Q.pop();
        if(vis[now.sd]) continue;
        vis[now.sd]=1;
        for(int i=ohead[now.sd];~i;i=OE[i].nxt) {
            int to=OE[i].y;
            if(dis[to]>dis[now.sd]+OE[i].l) {
                dis[to]=dis[now.sd]+OE[i].l;
                if(!vis[to]) Q.push(mkpr(dis[to], to));
            }
        }
    }
}

inline void Kruskal() {
    sort(eid+1, eid+1+m, cmp);
    top=n;
    for(int i=1;i<=m;++i) {
        int x=OE[eid[i]].x, y=OE[eid[i]].y;
        int fx=getfa(x), fy=getfa(y);
        if(fx!=fy) {
            fa[fx]=fy;
            ++top;
            nh[top]=OE[eid[i]].h;
            addedge(idx[fx], top, OE[eid[i]].l, OE[eid[i]].h);
            addedge(top, idx[fx], OE[eid[i]].l, OE[eid[i]].h);
            addedge(idx[fy], top, OE[eid[i]].l, OE[eid[i]].h);
            addedge(top, idx[fy], OE[eid[i]].l, OE[eid[i]].h);
            idx[fy]=top;
        }
    }
}

inline void DFS(int x, int f) {
    mnd[x]=x<=n ? dis[x] : 0x7f7f7f7f7f7f7f7f;
    anc[x][0]=f;
    for(int i=1;i<20;++i) {
        anc[x][i]=anc[anc[x][i-1]][i-1];
    }
    for(int i=head[x];~i;i=E[i].nxt) {
        int to=E[i].y;
        if(to!=f) {
            DFS(to, x);
            mnd[x]=min(mnd[x], mnd[to]);
        }
    }
}

int main() {
    // freopen("return.in", "r", stdin);
    // freopen("return.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while(T--) {
        memset(ohead, -1, sizeof ohead);
        memset(head, -1, sizeof head);
        tot=0;
        scanf("%d%d", &n, &m);
        for(int i=1, w, x, y, z;i<=m;++i) {
            scanf("%d%d%d%d", &w, &x, &y, &z);
            addoedge(w, x, y, z);
            eid[i]=tot;
            addoedge(x, w, y, z);
        }
        tot=0;
        Dijkstra();
        for(int i=1;i<=n;++i) {
            nh[i]=0x7f7f7f7f;
            fa[i]=i;
            idx[i]=i;
            // printf("%lld ", dis[i]);
        }
        Kruskal();
        DFS(top, 0);
        scanf("%d%d%d", &q, &k, &s);
        int lastans=0;
        for(int i=1, qv, qp;i<=q;++i) {
            scanf("%d%d", &qv, &qp);
            if(k) {
                qv=(qv-1+lastans)%n+1;
                qp=(qp+lastans)%(s+1);
            }
            for(int j=19;j>=0;--j) {
                if(anc[qv][j] && nh[anc[qv][j]]>qp) {
                    qv=anc[qv][j];
                }
            }
            // printf("-> %d\n", qv);
            printf("%lld\n", mnd[qv]);
            lastans=mnd[qv];
        }
    }
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}

评测结果