代码

//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   std::make_pair
#define orz  1000000007
#define fi   first
#define se   second
//using namespace std;
int n,m,q,k,s,la,d[200005],cnt,ans[400005],le[400005],pa[200005],f[400005][20];
std::pair<int,std::pair<int,int> >p[400005];
std::vector<int> v[200005],e[200005];
int get(int x){return x==pa[x]?x:pa[x]=get(pa[x]);}
int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        la=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i){
            int x,y,z,l;
            scanf("%d%d%d%d",&x,&y,&z,&l);
            p[i]=mp(-l,mp(x,y));
            v[x].pb(y),v[y].pb(x);
            e[x].pb(z),e[y].pb(z);
        }
        memset(d,-1,sizeof(d));
        d[1]=0;
        std::priority_queue<std::pair<int,int> >pq;
        pq.push(mp(0,1));
        while(!pq.empty()){
            int x=pq.top().se,y=-pq.top().fi;
            pq.pop();
            if(d[x]!=y) continue;
            for(int i=0;i<v[x].size();++i){
                if(d[v[x][i]]==-1||d[v[x][i]]>y+e[x][i]){
                    d[v[x][i]]=y+e[x][i];
                    pq.push(mp(-d[v[x][i]],v[x][i]));
                }
            }
        }
        sort(p+1,p+m+1);
        for(int i=1;i<=n;++i)pa[i]=i,ans[i]=d[i],le[i]=orz;
        cnt=n;
        for(int i=1;i<=m;++i){
            int x=p[i].se.fi,y=p[i].se.se;
            int X=get(x),Y=get(y);
            if(X==Y) continue;
            ++cnt;
            ans[cnt]=std::min(ans[X],ans[Y]);
            le[cnt]=-p[i].fi;
            pa[X]=pa[Y]=pa[cnt]=cnt;
            f[X][0]=f[Y][0]=cnt;
        }
        for(int i=0;i<18;++i){
            for(int j=1;j<=cnt;++j)f[j][i+1]=f[f[j][i]][i];
        }
        scanf("%d%d%d",&q,&k,&s);
        while(q--){
            int x,y;
            scanf("%d%d",&x,&y);
            x=(x+k*1ll*la-1ll)%n+1;
            y=(y+k*1ll*la)%(s+1);
            for(int i=18;i>=0;--i){
                if(f[x][i]&&le[f[x][i]]>y)x=f[x][i];
            }
            la=ans[x];
            printf("%d\n",la);
        }
    }
	//system("pause");
	return 0;
}

评测结果