代码

// luogu-judger-enable-o2
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m;int q;int t;int k;
int a[800010];
int lastans;
int s;

struct data{
    int v;int value;int next;
    friend bool operator <(const data &a,const data &b) {return a.value>b.value;}
}edge[800010];int alist1[800010];int cnt1;
void add1(int u,int v,int value)
{
    edge[++cnt1].v=v;
    edge[cnt1].value=value;
    edge[cnt1].next=alist1[u];
    alist1[u]=cnt1;
    return ;
} 

struct qwq{
    int v;int next;
}qwq[1600010];int alist2[1600010];int cnt2;
void add2(int u,int v)
{
    qwq[++cnt2].v=v;
    qwq[cnt2].next=alist2[u];
    alist2[u]=cnt2;
//	printf("%d %d %d\n",u,v,cnt2);
    return ;
}

struct node{
    int u;int v;int l;int val;
    friend bool operator <(const node &a,const node &b) {return a.val>b.val;}
}node[400010],point[1600010];

struct pair1{
    int first;int second;
    friend bool operator <(const pair1 &a,const pair1 &b) {return a.second>b.second;}
};

priority_queue<pair1> qaq;
bool ins[800010];int dis[800010];
void dijstra()
{
    memset(ins,false,sizeof(ins));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[1]=0;
    pair1 s={1,0};
    qaq.push(s);
    while(!qaq.empty())
    {
        pair1 x=qaq.top();
        qaq.pop();
        if(!ins[x.first])
        {
            ins[x.first]=true;
            int next=alist1[x.first];
            while(next)
            {
                int v=edge[next].v;
                if(!ins[v]&&dis[v]>dis[x.first]+edge[next].value) 
                    dis[v]=dis[x.first]+edge[next].value,
                    qaq.push((pair1){v,dis[v]});
                next=edge[next].next;
            }
        }
    }
    for(int i=1;i<=n;i++) point[i].l=dis[i];
    return ;
}

int depth[800010];int dp[400010][20];
void dfs(int u,int f)
{
//	printf("%d %d\n",u,f);
    depth[u]=depth[f]+1;
    dp[u][0]=f;
    for(int i=1;i<=19;i++) dp[u][i]=dp[dp[u][i-1]][i-1];
    for(int i=alist2[u];i;i=qwq[i].next)
    {
//		printf("quq? %d %d\n",next,qwq[next].v);
        dfs(qwq[i].v,u);
        point[u].l=min(point[u].l,point[qwq[i].v].l);
    }
    return ;
}

int quest(int x,int y)
{
//	printf("quq? %d %d\n",x,y);
    for(int i=19;i>=0;i--) {
//		printf("lalala:  %d %d %d %d %d\n",i,depth[x],(1<<i),point[dp[x][i]].val,y);
      if(depth[x]>(1<<i) && point[dp[x][i]].val>y)
            x=dp[x][i];
      	
      }
    return point[x].l;
}

int fa[1600010];int tot=0;
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
bool che(int x,int y) {return find(x)==find(y);}
int count1=n;
void merge(int x,int y)
{
    int fx=find(x);int fy=find(y);
    count1++;
//	printf("qaq: %d %d %d\n",count1,fx,fy);
    add2(count1,fx);
    add2(count1,fy);
    fa[fx]=count1;
    fa[fy]=count1;
    tot++;
}

int opt;
void kruskal()
{
    
    for(int i=1;i<=(n<<1);i++)
        fa[i]=i;
//	for(int i=1;i<=(n<<1);i++) printf("%d ",fa[i]);
    sort(node+1,node+m+1);
//	for(int i=1;i<=m;i++) printf("%d %d %d %d\n",node[i].u,node[i].v,node[i].val,node[i].l);
    for(int i=1;i<=m;i++){
        int u=node[i].u;
        int v=node[i].v;
//		for(int j=1;j<=(n<<1);j++) printf("%d ",fa[j]);puts("");
        int fu=find(u);int fv=find(v);
//		printf("qwq: %d %d\n",fu,fv);
        if(fu!=fv)
        {
            merge(node[i].u,node[i].v);
            point[count1].val=node[i].val;
    }
        if(tot==n-1)break;
    }
    dfs(count1,0);
    while(q--)
    {
        scanf("%d",&opt);
        int x=(lastans*k+opt-1)%n+1;
        scanf("%d",&opt);
        int y=(lastans*k+opt)%(s+1);
//		printf("qwq: %d %d %d\n",x,y,s);
        int ans=quest(x,y);
        printf("%d\n",ans);
        lastans=ans;
    }
}

void clear(int n)
{
    lastans=0;
    memset(node,0,sizeof(qwq));
    memset(alist1,0,sizeof(alist1));
    memset(alist2,0,sizeof(alist2));
    memset(dp,0,sizeof(dp));
    cnt1=0;cnt2=0;count1=n;
    for(int i=n+1;i<=(n<<1);i++) point[i].l=0x3f3f3f3f;
    return ;
}
int main()
{

//	freopen("return5.in","r",stdin);
//	freopen("return5.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {	
        scanf("%d%d",&n,&m);
        clear(n);
        for(int i=1;i<=m;i++)
          scanf("%d%d%d%d",&node[i].u,&node[i].v,&node[i].l,&node[i].val),
          add1(node[i].u,node[i].v,node[i].l),
          add1(node[i].v,node[i].u,node[i].l);
        dijstra();
        scanf("%d%d%d",&q,&k,&s);
        kruskal();
    }
    return 0;
} 

评测结果