代码

#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<queue>
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=800005;
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];
std::vector<Edge>edges;
std::vector<int>G[maxn]; 
int n,m,T,fa[maxn],anc[maxn],val[maxn],dis[maxn],hei[maxn],g[maxn][20],q,k,s;
bool 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;
	}
};
std::priority_queue<Node>Q;
inline void Dijkstra() {
	while(!Q.empty())
		Q.pop();
	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;
		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 int gf(int x) {
	return x==fa[x]?x:fa[x]=gf(fa[x]);
}
int main() {
	read(T);
	while(T--) {
		read(n),read(m);
		edges.clear();
		for(int i=1;i<=n;++i)
			G[i].clear();
		for(int i=1;i<=m;++i)
			read(E[i].u),read(E[i].v),read(E[i].l),read(E[i].a);
		read(q),read(k),read(s); 
		std::sort(E+1,E+m+1);
		for(int i=1;i<=m;++i) {
			edges.push_back(Edge(E[i].u,E[i].v,E[i].l));
			G[E[i].u].push_back(edges.size()-1);
			edges.push_back(Edge(E[i].v,E[i].u,E[i].l));
			G[E[i].v].push_back(edges.size()-1);
		}
		Dijkstra();
		for(int i=1;i<=n;++i)
			fa[i]=anc[i]=i;
		int cnt=n;
		for(int i=1;i<=m;++i) {
			int u=E[i].u,v=E[i].v;
			cnt++,fa[cnt]=cnt,fa[u]=gf(u),fa[v]=gf(v);
			dis[cnt]=std::min(dis[fa[u]],dis[fa[v]]);
			anc[cnt]=anc[fa[u]]=anc[fa[v]]=cnt;
			fa[fa[u]]=fa[fa[v]]=cnt;
			hei[cnt]=E[i].a;
		}
		for(int i=1;i<=cnt;++i)
			g[i][0]=anc[i];
		for(int i=1;i<20;++i)
			for(int j=1;j<=cnt;++j)
				g[j][i]=g[g[j][i-1]][i-1];
		for(int i=1;i<=n;++i)
			hei[i]=s+1;
		int lstans=0;
		while(q--) {
			int x,y;
			read(x),read(y);
			x=(x+k*lstans-1)%n+1;
			y=(y+k*lstans)%(s+1);
			for(int i=19;~i;--i)
				if(hei[g[x][i]]>y)
					x=g[x][i];
			printf("%d\n",lstans=dis[x]);
		}
	}
}

评测结果