代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;
const int M=800000+10; //两倍空间
const int INF=0x3f3f3f3f;

struct Save_Edge { int u,v,l,a; };
struct Edge { int v,w,nxt; };
struct HeapNode { int u,d; };
struct Node { int l,a; };

bool operator <(Save_Edge a,Save_Edge b) { return a.a>b.a; }
bool operator <(HeapNode a,HeapNode b) { return a.d>b.d; }

int n,m;
Save_Edge E[M];
Edge e[M<<1];
int head[N],cnt=0;
Node p[N];
int inq[N],dis[N],fa[N],dep[N],f[20][N];

inline void clearGraph() { memset(head,0,sizeof(head)); cnt=0; }
inline void addEdge(int u,int v,int w=0) {
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}
inline int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); }
inline void merge(int x,int y) { x=find(x),y=find(y); if (x!=y) fa[x]=y; }
inline void Dijkstra() {
    memset(inq,0,sizeof(inq)); inq[1]=0;
    memset(dis,0x3f,sizeof(dis)); dis[1]=0;
    priority_queue<HeapNode> Q; Q.push((HeapNode){1,0});
    while (!Q.empty()) {
        int u=Q.top().u,d=Q.top().d; Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (d+w<dis[v]) {
                dis[v]=d+w;
                if (!inq[v]) Q.push((HeapNode){v,d+w});
            }
        }
    }
    for (re int i=1;i<=n;++i) p[i].l=dis[i];
}
inline void dfs(int u,int fa) {
    dep[u]=dep[fa]+1,f[0][u]=fa;
    for (re int i=1;i<=19;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; dfs(v,u); p[u].l=min(p[u].l,p[v].l);
    }
}
inline void Build() { //建树
    clearGraph();
    int tot=0,cnt=n; sort(E+1,E+m+1);
    for (re int i=1;i<=(n<<1);++i) fa[i]=i;
    for (re int i=1;i<=m;++i) {
        int u=find(E[i].u),v=find(E[i].v);
        if (u!=v) {
            addEdge(++cnt,u),addEdge(cnt,v);
            merge(u,cnt),merge(v,cnt);
            p[cnt].a=E[i].a,++tot;
        }
        if (tot==n-1) break;
    }
    dfs(cnt,0);
}
inline int query(int v,int s) {
    for (re int i=19;i>=0;--i)
        if (dep[v]>(1<<i)&&p[f[i][v]].a>s) v=f[i][v];
    return p[v].l;
}

int main() {
    int T=read();
    while (T--) {
        clearGraph(); memset(f,0,sizeof(f)); memset(E,0,sizeof(E));
        n=read(),m=read();
        for (re int i=1;i<=m;++i) {
            E[i].u=read(),E[i].v=read(),E[i].l=read(),E[i].a=read();
            addEdge(E[i].u,E[i].v,E[i].l); addEdge(E[i].v,E[i].u,E[i].l);
        }
        for (re int i=n+1;i<=(n<<1);++i) p[i].l=INF;
        Dijkstra(); Build();
        int Q=read(),K=read(),S=read(),lastans=0;
        while (Q--) {
            int v=(read()+K*lastans-1)%n+1;
            int s=(read()+K*lastans)%(S+1);
            printf("%d\n",lastans=query(v,s));
        }
    }
    return 0;
}

评测结果