代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm> 
#include<cmath>
#include<queue>
#include<vector>
#define re register
#define il inline
#define LL long long
#define inf 999999999

using namespace std;
const LL mod=998244853;
il LL rd()
{
    LL x=0,t=1; char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct nnn
{
  int x,y,l,a;
}e[400010];
il bool ccmp(nnn a,nnn b){return a.a>b.a;}
int n,m;
int to[800010],nt[800010],w[800010],hd[200010],di[400010],tot=1;
il void add(int x,int y,int z)
{
  ++tot;to[tot]=y;nt[tot]=hd[x];w[tot]=z;hd[x]=tot;
  ++tot;to[tot]=x;nt[tot]=hd[y];w[tot]=z;hd[y]=tot;
}
struct cmp
{
  bool operator ()(const int x,const int y)
  {
    return di[x]>di[y];
  }
};
priority_queue<int,vector<int>,cmp> q;
bool v[200010];
il void dj()
{
  memset(di,0x3f3f3f,sizeof(di));
  di[1]=0;
  q.push(1),v[1]=true;
  while(!q.empty())
    {
      int x=q.top();
      q.pop();
      v[x]=false;
      for(int i=hd[x];i;i=nt[i])
    {
      int y=to[i];
      if(di[y]>di[x]+w[i])
        {
          di[y]=di[x]+w[i];
          if(!v[y]) q.push(y);
          v[y]=true;
        }
    }
    }
}
int fa[400010],aa[400010],tt,f[400010][20],ans;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merg(int x,int y){fa[find(x)]=find(y);}

int main()
{
  int T=rd();
  while(T--)
    {
      ans=0;
      tot=1;
      memset(hd,0,sizeof(hd));
      tt=n=rd(),m=rd();
      int nn=log(n)/log(2)+1;
      for(int i=1;i<=n<<1;i++) fa[i]=i;
      for(int i=1;i<=m;i++)
    {
      int x=rd(),y=rd(),l=rd(),a=rd();
      e[i]=(nnn){x,y,l,a};
      add(x,y,l);
    }
      dj();
      sort(e+1,e+m+1,ccmp);
      for(int i=1,j=n-1;i<=m;i++)
    {
      if(find(e[i].x)==find(e[i].y)) continue;
      ++tt;
      di[tt]=min(di[find(e[i].x)],di[find(e[i].y)]);
      aa[tt]=e[i].a;
      fa[find(e[i].x)]=fa[find(e[i].y)]=f[find(e[i].x)][0]=f[find(e[i].y)][0]=tt;
          --j;
      if(!j) break;
    }
      f[tt][0]=0;aa[0]=-inf;
      for(int j=1;j<=nn;j++)
    for(int i=1;i<=tt;i++)
      f[i][j]=f[f[i][j-1]][j-1];
      int q=rd(),k=rd(),s=rd();
      while(q--)
    {
          int v=(rd()+k*ans-1)%n+1,p=(rd()+k*ans)%(s+1);
      ans=0;
      int o=v;
      for(int j=nn;j>=0;j--)
        if(aa[f[o][j]]>p) o=f[o][j];
      printf("%d\n",ans=di[o]);
    }
    }
  return 0;
}

评测结果