代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
namespace IAOI_lib{
  class dsu{
    private:
      vector<int> a,s;
    public:
      dsu(int n):a(n),s(n,1){
        iota(a.begin(),a.end(),0);
      }
      int leader(int x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      int size(int x){
        return s[leader(x)];
      }
      void merge(int x,int y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      bool same(int x,int y){
        return leader(x)==leader(y);
      }
  };
}
main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,m,c,lst=0; cin>>n>>m,c=n;
    vector<vector<tpi> > g(n);
    vector<tpi> e(n);
    for(int i=0;i<m;i++){
      int u,v,l,a; cin>>u>>v>>l>>a;
      e.emplace_back(a,--u,--v);
      g[u].emplace_back(v,l,a);
      g[v].emplace_back(u,l,a);
    }
    vector<pii> f(n<<1,make_pair(1e16,0));
    vector<bool> b(n);
    priority_queue<pii,vector<pii>,greater<> > Q;
    Q.emplace(f[0].first=0,0);
    while(!Q.empty()){
      int u=Q.top().second; Q.pop();
      if(b[u])continue; b[u]=true;
      for(auto [i,l,a]:g[u])
        if(f[i].first>f[u].first+l)
          Q.emplace(f[i].first=f[u].first+l,i);
    }
    sort(e.begin(),e.end(),greater<>());
    IAOI_lib::dsu<int> mst(n<<1);
    vector<vector<int> > t(n<<1);
    for(auto [w,u,v]:e)
      if(!mst.same(u,v)){
        t[c].emplace_back(mst.leader(u));
        t[c].emplace_back(mst.leader(v));
        mst.merge(c,u,v);
        f[c].second=w;
        if(++c==n<<1)break;
      }
    vector<int> d(n<<1);
    int l=__lg(n)+1; vector s(n<<1,vector<int>(l+1));
    function<void(int,int)> dfs=[&](int u,int r){
      s[u][0]=r; for(int i=1;i<=l;i++)
        s[u][i]=s[s[u][i-1]][i-1];
      for(int i:t[u])
        dfs(i,u),f[u].first=min(f[u].first,f[i].first);
    };
    dfs(n-1<<1,n-1<<1);
    int q,k,h; cin>>q>>k>>h;
    while(q--){
      int v,p; cin>>v>>p;
      (v+=k*lst-1)%=n,(p+=k*lst)%=h+1;
      for(int i=l;~i;i--)
        if(f[s[v][i]].second>p)v=s[v][i];
      cout<<(lst=f[v].first)<<'\n';
    }
  }
  return 0;
}

评测结果