代码

//#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<assert.h>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1LL<<62;
const int mod=1e9+7;

const int N=2e5+100,M=8e5+100;

int qpow(int x,int y) {
	int ans=1;
	while (y) {
		if (y&1) ans=1LL*ans*x%mod;
		x=1LL*x*x%mod;y>>=1;
	}
	return ans;
}

int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

namespace io {
	const int L=(1<<21)+1;
	char ibuf[L],*iS,*iT,obuf[L],*oS=obuf,*oT=obuf+L-1,c,st[55];int f,tp;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,L,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline char getc() {
		return gc();
	}
	inline void flush() {
		fwrite(obuf,1,oS-obuf,stdout);
		oS=obuf;
	}
	inline void putc(char x) { *oS++=x; if (oS==oT) flush(); }
	template<class I> inline void gi(I&x) {
		for (f=1,c=gc();c<'0'||c>'9';c=gc()) if (c=='-') f=-1;
		for (x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15); x*=f;
	}
	template<class I> inline void print(I x) {
		if (!x) putc('0');
		if (x<0) putc('-'),x=-x;
		while (x) st[++tp]=x%10+'0',x/=10;
		while (tp) putc(st[tp--]);
	}
	inline void gs(char*s, int&l) {
		for (c=gc();c<'a'||c>'z';c=gc());
		for (l=0;c<='z'&&c>='a';c=gc()) s[l++]=c;
		s[l]=0;
	}
	inline void ps(const char*s) { for (int i=0,n=strlen(s);i<n;i++) putc(s[i]); }
	struct IOFLUSHER{ ~IOFLUSHER() { flush(); } } _ioflusher_;
};
using io::getc;
using io::putc;
using io::gi;
using io::gs;
using io::ps;
using io::print;

int head[N],nxt[M],to[M],w[M];
bool out[N];int dis[N*2];

struct Q{ int k,dis; bool operator < (const Q &b) const { return dis>b.dis; } };
priority_queue<Q>q;

struct E{ int u,v,w; }e[M];

int fa[N*2];int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }
int G[N*2][20],H[N*2][20];
int main()
{
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	int T,n,m,i,k,a,b,tot,op,S,ans,v,p,t,nn;
	gi(T);
	while (T--) {
		gi(n),gi(m);nn=n;
		
		for (i=1;i<=n;i++) head[i]=0,fa[i]=i,dis[i]=oo,out[i]=false,G[i][0]=0;
		tot=0;
		
		for (i=1;i<=m;i++) {
			gi(a),gi(b),gi(k);
			to[++tot]=b,nxt[tot]=head[a],head[a]=tot,w[tot]=k;
			to[++tot]=a,nxt[tot]=head[b],head[b]=tot,w[tot]=k;
			e[i].u=a,e[i].v=b,gi(e[i].w);
		}
		sort(e+1,e+1+m,[&](E a,E b){return a.w<b.w;});

		for (q.push((Q){1,dis[1]=0});!q.empty();) {
			k=q.top().k;q.pop();
			if (out[k]) continue;out[k]=true;
			for (i=head[k];i;i=nxt[i])
				if (dis[k]+w[i]<dis[to[i]])
					q.push((Q){to[i],dis[to[i]]=dis[k]+w[i]});
		}
		
		for (i=m;i;i--)
			if ((a=find(e[i].u))^(b=find(e[i].v))) {
				dis[++n]=min(dis[a],dis[b]);
				fa[a]=fa[b]=fa[n]=n;
				G[a][0]=G[b][0]=n;G[n][0]=0;
				H[a][0]=H[b][0]=e[i].w;
			}

		for (t=1;t<20;t++)
			for (i=1;i<=n;i++)
				G[i][t]=G[G[i][t-1]][t-1],H[i][t]=H[G[i][t-1]][t-1];
		
		for (gi(m),gi(op),gi(S),ans=0;m--;) {
			gi(v),v=(v+op*ans-1)%nn+1;
			gi(p),p=(p+op*ans)%(S+1);
			for (t=19;~t;t--)
				if (G[v][t]&&H[v][t]>p)
					v=G[v][t];
			print(ans=dis[v]);putc('\n');
		}
	}
	return 0;
}

评测结果