代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF=1e14;
const int N=5e5;
const int M=1e6;
int t,tot,n,m;
int head[N+10];
struct data {
    int next,num;
    LL w;
}edge[M+10];
void Add(int u,int v,LL w) {
    edge[++tot].next=head[u];
    edge[tot].num=v;
    edge[tot].w=w;
    head[u]=tot;
}
struct node {
    LL dis;
    int loc;
    bool operator < (const node &p) const {
        return dis>p.dis;
    }
};
struct edges {
    int u,v;
    LL l,ax;
}e[M+10];
bool cmp(edges p,edges q) {
    return p.ax>q.ax;
}
priority_queue <node> q;
LL dis[N+10];
void Dijkstra() {
    for (int i=1;i<=n;i++) dis[i]=INF;
    dis[1]=0;
    node now;
    now.dis=0;
    now.loc=1;
    q.push(now);
    while (!q.empty()) {
        node now=q.top();
        q.pop();
        while (!q.empty()&&now.dis!=dis[now.loc]) {
            now=q.top();
            q.pop();
        }
        if (now.dis!=dis[now.loc]) break;
        for (int i=head[now.loc];i!=-1;i=edge[i].next) {
            int kx=edge[i].num;
            if (now.dis+edge[i].w<dis[kx]) {
                dis[kx]=now.dis+edge[i].w;
                node dx;
                dx.dis=dis[kx];
                dx.loc=kx;
                q.push(dx);
            }
        }
    }
}
vector <pair<int,int> > fa[N+10];
vector <pair<int,int> > min0[N+10];
vector <pair<int,int> > sz[N+10];
int GETF(int x) {
    if (fa[x][fa[x].size()-1].first==x) return x;
    return GETF(fa[x][fa[x].size()-1].first);
}
void prework() {
    for (int i=1;i<=n;i++) {
        fa[i].clear();
        min0[i].clear();
        sz[i].clear();
        fa[i].push_back(make_pair(i,0));
        min0[i].push_back(make_pair(dis[i],0));
        sz[i].push_back(make_pair(1,0));
    }
    sort(e+1,e+m+1,cmp);
    for (int i=1;i<=m;i++) {
        int u=e[i].u,v=e[i].v;
        int fu=GETF(u),fv=GETF(v);
        if (fu==fv) continue;
        if (sz[fu][sz[fu].size()-1].first>sz[fv][sz[fv].size()-1].first)
            swap(fu,fv);
        fa[fu].push_back(make_pair(fv,i));
        int minx=min0[fu][min0[fu].size()-1].first;
        minx=min(minx,min0[fv][min0[fv].size()-1].first);
        min0[fv].push_back(make_pair(minx,i));
        int nowsz=sz[fu][sz[fu].size()-1].first+sz[fv][sz[fv].size()-1].first;
        sz[fv].push_back(make_pair(nowsz,i));
    }
}
int getff(int x,int lim) {
    int l=0,r=fa[x].size()-1;
    while (l<r) {
        int mid=(l+r+1)/2;
        if (fa[x][mid].second<=lim) l=mid;
        else r=mid-1;
    }
    return fa[x][l].first;
}
int getmin0(int x,int lim) {
    int l=0,r=min0[x].size()-1;
    while (l<r) {
        int mid=(l+r+1)/2;
        if (min0[x][mid].second<=lim) l=mid;
        else r=mid-1;
    }
    return min0[x][l].first;
}
int getf(int x,int lim) {
    int ff=getff(x,lim);
    if (x==ff) return x;
    return getf(ff,lim);
}
int Calc(int px,int lim) {
    int fu=getf(px,lim);
    return getmin0(fu,lim);
}
void work() {
    int q,k,s;
    scanf("%d%d%d",&q,&k,&s);
    LL lst=0;
    while (q--) {
        LL v0,p0;
        scanf("%lld%lld",&v0,&p0);
        LL v=(v0+k*lst+n-1)%n+1;
        LL p=(p0+k*lst)%(s+1);
        int l=0,r=m;
        while (l<r) {
            int mid=(l+r+1)/2;
            if (e[mid].ax>p) l=mid;
            else r=mid-1;
        }
        int ans=Calc(v,l);
        printf("%d\n",ans);
        lst=ans;
    }
}
int main() {
    //freopen("return.in","r",stdin);
    //freopen("return.out","w",stdout);
    scanf("%d",&t);
    while (t--) {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) head[i]=-1;
        tot=0;
        for (int i=1;i<=m;i++) {
            scanf("%d%d%lld%lld",&e[i].u,&e[i].v,&e[i].l,&e[i].ax);
            Add(e[i].u,e[i].v,e[i].l);
            Add(e[i].v,e[i].u,e[i].l);
        }
        Dijkstra();
        prework();
        work();
    }
    return 0;
}

评测结果