代码

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=200005;
int n,m,q,k,s;
struct Edge {
	int u,v,l,a;
	Edge(int u=0,int v=0,int l=0,int a=0):u(u),v(v),l(l),a(a){}
	inline bool operator < (const Edge &rhs) const {
		return a>rhs.a;
	}
}e[maxn<<1];
vector<Edge>edges;
vector<int>G[maxn];
namespace offline {
	ll dis[maxn],ans[maxn];
	bool vis[maxn];
	int fa[maxn];
	struct Node {
		int u;
		ll d;
		Node(int u=0,ll d=0):u(u),d(d){}
		inline bool operator < (const Node &rhs) const {
			return d>rhs.d;
		}
	};
	struct Query {
		int v,p,id;
		inline bool operator < (const Query &rhs) const {
			return p>rhs.p;
		}
	}ask[maxn];
	priority_queue<Node>Q;
	inline int gf(int x) {
		return x==fa[x]?x:fa[x]=gf(fa[x]);
	}
	inline void solve() {
		while(!Q.empty())
			Q.pop();
		//cerr<<"In to solve."<<endl;
		memset(dis,0x3f,sizeof dis);
		memset(vis,0,sizeof vis);
		dis[1]=0;
		Q.push(Node(1,0));
		while(!Q.empty()) {
			Node now=Q.top();
			Q.pop();
			int u=now.u;
			ll d=now.d;
			//cerr<<"???"<<u<<" "<<d<<endl;
			if(vis[u])
				continue;
			vis[u]=1;
			for(int i=0;i<(int)G[u].size();++i) {
				Edge &e=edges[G[u][i]];
				int v=e.v;
				if(dis[v]>d+e.l) {
					dis[v]=d+e.l;
					Q.push(Node(v,dis[v]));
				}
			}
		}
		for(int i=1;i<=q;++i)
			read(ask[i].v),read(ask[i].p),ask[i].id=i;
		//cerr<<"Read done."<<endl;
		sort(e+1,e+m+1);
		sort(ask+1,ask+q+1);
		for(int i=1;i<=n;++i)
			fa[i]=i;
		int pos=1;
		for(int i=1;i<=q;++i) {
			//cerr<<i<<" "<<pos<<endl;
			while(pos<=m&&e[pos].a>ask[i].p) {
				//cerr<<pos<<endl;
				int u=gf(e[pos].u),v=gf(e[pos].v);
				if(u==v) {
					pos++;
					continue;
				}
				if(dis[u]<dis[v])
					fa[v]=u;
				else
					fa[u]=v;
				pos++;
			}
			ans[ask[i].id]=dis[gf(ask[i].v)];
		}
		for(int i=1;i<=q;++i)
			printf("%lld\n",ans[i]);
	}
}
namespace tree {
	int anc[maxn][20],mn[maxn][20];
	ll dis[maxn];
	inline void dfs(int u) {
		for(int i=1;i<20;++i)
			anc[u][i]=anc[anc[u][i-1]][i-1],mn[u][i]=min(mn[u][i-1],mn[anc[u][i-1]][i-1]);
		for(int i=0;i<(int)G[u].size();++i) {
			Edge &e=edges[G[u][i]];
			int v=e.v,l=e.l,a=e.a;
			if(v==anc[u][0])
				continue;
			anc[v][0]=u;
			mn[v][0]=a;
			dis[v]=dis[u]+l;
//			cout<<v<<" "<<u<<" "<<dis[v]<<" "<<dis[u]<<" "<<w<<endl;
			dfs(v);
		}
	}
	inline int work(int x,int p) {
		for(int i=19;~i;--i)
			if(mn[x][i]>p)
				x=anc[x][i];
//		cout<<"Final :"<<x<<endl;
		return x;
	}
	inline void solve() {
		memset(mn,0x3f,sizeof mn);
		anc[1][0]=0;
		dis[1]=0;
		dfs(1);
//		for(int i=1;i<=n;++i,puts(""))
//			for(int j=0;j<20;++j)
//				printf("%d ",mn[i][j]);
		int v,p;
		ll lstans=0;
		while(q--) {
			read(v),read(p);
			v=(v+k*lstans-1)%n+1;
			p=(p+k*lstans)%(s+1);
//			cerr<<"Unlock :"<<v<<" "<<p<<endl;
			printf("%lld\n",lstans=dis[work(v,p)]);
		}
	}
}
inline void File() {
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
}
ll dis[maxn];
int vis[maxn];
struct Node {
	int u;
	ll d;
	Node(int u=0,ll d=0):u(u),d(d){}
	inline bool operator < (const Node &rhs) const {
		return d>rhs.d;
	}
};
priority_queue<Node>Q;
inline void dijkstra() {
	while(!Q.empty())
		Q.pop();
	//cerr<<"In to solve."<<endl;
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[1]=0;
	Q.push(Node(1,0));
	while(!Q.empty()) {
		Node now=Q.top();
		Q.pop();
		int u=now.u;
		ll d=now.d;
		//cerr<<"???"<<u<<" "<<d<<endl;
		if(vis[u])
			continue;
		vis[u]=1;
		for(int i=0;i<(int)G[u].size();++i) {
			Edge &e=edges[G[u][i]];
			int v=e.v;
			if(dis[v]>d+e.l) {
				dis[v]=d+e.l;
				Q.push(Node(v,dis[v]));
			}
		}
	}
}
inline ll brute(int x,int lim,int T) {
	ll ans=1e12;
	queue<int>q;
	q.push(x);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
//		cout<<"Bfs :"<<u<<endl;
		if(vis[u]==T)
			continue;
		vis[u]=T;
		ans=min(ans,dis[u]);
		for(int i=0;i<(int)G[u].size();++i) {
			Edge &e=edges[G[u][i]];
			int a=e.a,v=e.v;
			if(a>lim&&vis[v]!=T)
				q.push(v);
		}
	}
	return ans;
}
int main() {
//	freopen("offline.in","r",stdin);
//	freopen("offline.out","w",stdout);
	int T;
	read(T);
	while(T--) {
		edges.clear();
		read(n),read(m);
		for(int i=1;i<=n;++i)
			G[i].clear();
		for(int i=1,u,v,l,a;i<=m;++i) {
			read(u),read(v),read(l),read(a);
			e[i]=Edge(u,v,l,a);
			edges.push_back(Edge(u,v,l,a));
			G[u].push_back(edges.size()-1);
			edges.push_back(Edge(v,u,l,a));
			G[v].push_back(edges.size()-1);
		}
		read(q),read(k),read(s);
		if(!k) {
			offline::solve();
			continue;
		}
		if(n==m+1) {
			tree::solve();
			continue;
		}
		dijkstra();
		int v,p;
		ll lstans=0;
		for(int i=1;i<=q;++i) {
			read(v),read(p);
			v=(v+k*lstans-1)%n+1;
			p=(p+k*lstans)%(s+1);
			printf("%lld\n",lstans=brute(v,p,i+1));
		}
	}
}

评测结果