代码

#include<cstdio>
#include<vector>
#include<cctype>
#include<cstring>
#include<set>
#include<map>
#include<bitset>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M=4e5+500,N=2e5+500;

//Do not use it while there are any strings
ll gti(void)
{
/*    static const int S=1<<16;
    static char buf[S],*p=buf+S;
#define getchar() ((p==buf+S?fread(p=buf,1,S,stdin):0),*p++)*/
    ll st=1,ret=0;
    char c=getchar();
    for (;!isdigit(c)&&c!='-';c=getchar());
    if (c=='-') st=-1,c=getchar();
    for (;isdigit(c);c=getchar()) ret=ret*10+c-'0';
//#undef getchar
    return ret*st;
}

int n,m;

struct edge
{
    edge *nxt;
    int f,t,l,a;
    bool operator<(const edge &b)const
    {
    return a>b.a;
    }
}pool[M*2],*pt[N],*p=pool,e[M];
void add(int a,int b,int c)
{
    *(++p)=(edge){pt[a],a,b,c,0},pt[a]=p;
    *(++p)=(edge){pt[b],b,a,c,0},pt[b]=p;
}

int dis[N];
struct P
{
    int id,dis;
    P(void):id(0),dis(0x7fffffff){}
    P(int a,int b):id(a),dis(b){}
    bool operator<(const P &b)const
    {
    return dis>b.dis;
    }
};
priority_queue<P> hp;
int sum=0;
void dijstra(void)
{
    memset(dis,127,sizeof(dis));
    dis[1]=0;
    while (hp.size()) hp.pop();
    hp.push(P(1,0));
    for (P i;hp.size();)
    {
    ++sum;
    for (i=hp.top(),hp.pop();i.dis!=dis[i.id]&&hp.size();i=hp.top(),hp.pop());
    for (edge *x=pt[i.id];x;x=x->nxt)
        if (dis[x->t]>dis[i.id]+x->l)
        dis[x->t]=dis[i.id]+x->l,hp.push(P(x->t,dis[x->t]));
    }
}

int fa[N],zh[N];
int getfa(int v)
{
    return fa[v]==v?v:fa[v]=getfa(fa[v]);
}

#define mid ((l+r)>>1)
struct segt
{
    int ls,rs,f,v;
}t[N*50];
int cnt=0,rt[M];
int build(int now=0,int l=1,int r=n)
{
    now=++cnt;
    if (l==r) t[now]=(segt){0,0,l,dis[l]};
    else t[now].ls=build(0,l,mid),t[now].rs=build(0,mid+1,r);
    return now;
}
void change(int lst,int &now,int loc,segt x,int l=1,int r=n)
{
    if (!now) t[now=++cnt]=t[lst];
    else t[++cnt]=t[now],now=cnt;
    if (l==r) t[now]=x;
    else if (loc<=mid) change(t[lst].ls,t[now].ls,loc,x,l,mid);
    else if (loc>mid) change(t[lst].rs,t[now].rs,loc,x,mid+1,r);
}
segt query(int now,int v,int l=1,int r=n)
{
    if (l==r) return t[now];
    if (v<=mid) return query(t[now].ls,v,l,mid);
    return query(t[now].rs,v,mid+1,r);
}
void merge(int lst,int &now,int a,int b)
{
    int af=getfa(a),fb=getfa(b);
    if (af==fb) return;
    int val=min(query(lst,af).v,query(lst,fb).v);
    a=af,b=fb;
    if (zh[a]<zh[b]) swap(a,b);
    zh[a]=max(zh[a],zh[b]+1),fa[b]=a;
    segt x=(segt){0,0,a,val};
    change(lst,now,a,x),change(lst,now,b,x);
}

void init(void)
{
    p=pool,cnt=0;
    memset(pt,0,sizeof(pt));
    for (int i=1;i<=n;i++)
    fa[i]=i,zh[i]=0;
    for (int i=0;i<=m;i++) rt[i]=0;
}

int main(void)
{
    int T=gti();
    while (T--)
    {
    n=gti(),m=gti();
    init();
    for (int i=1;i<=m;i++)
    {
        int u=gti(),v=gti(),l=gti(),a=gti();
        add(u,v,l);
        e[i]=(edge){NULL,u,v,l,a};
    }
    dijstra();
    rt[0]=build();
    sort(e+1,e+1+m);
    for (int i=1;i<=m;i++)
        rt[i]=rt[i-1],merge(rt[i-1],rt[i],e[i].f,e[i].t);
    int q=gti(),tp=gti(),mx=gti(),ans=0;
    for (int i=1;i<=q;i++)
    {
        int v=(gti()+tp*ans-1)%n+1,p=(gti()+tp*ans)%(mx+1);
        edge now=(edge){NULL,0,0,0,p};
        int s=rt[(lower_bound(e+1,e+1+m,now)-e)-1];
        segt x=query(s,v);
        while (x.f!=v)
           	v=x.f,x=query(s,v);
        ans=x.v;
        printf("%d\n",ans);
    }
    }
    return 0;
}

评测结果