代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define LL long long
#define out(x) cerr<< #x << '=' << x << endl;
using namespace std;
const int N=2e5+10;
const LL inf=0x3f3f3f3f3f3f3f3f;

int n,m,E,q,k,s;
int fir[N],nex[N<<1],arr[N<<1],len[N<<1],high[N<<1],vis[N];
LL dis[N];
struct Eg {
	int x,y,high;
}e[N];
struct pnt {
	int x; LL d;
	bool operator < (pnt other) const {
		return d>other.d;
	}
};
queue<int> Q;
priority_queue<pnt> Heap;

inline void read(int &x) {
	char c=getchar();
	x=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
}

inline void Add_Edge(int x,int y,int l,int h) {
	nex[++E]=fir[x];
	fir[x]=E; arr[E]=y; len[E]=l; high[E]=h;
	nex[++E]=fir[y];
	fir[y]=E; arr[E]=x; len[E]=l; high[E]=h;
}

void Dijkstra() {
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0; Heap.push((pnt){1,0});
	while (!Heap.empty()) {
		int x=Heap.top().x; LL d=Heap.top().d; Heap.pop();
		if (dis[x]<d) continue;
		for (int i=fir[x];i;i=nex[i]) {
			if (dis[arr[i]]>dis[x]+len[i]) {
				dis[arr[i]]=dis[x]+len[i];
				Heap.push((pnt){arr[i],dis[arr[i]]});
			}
		}
	}
}

namespace Subtask1 {
	int lastans=0,vis[N];

	void bfs(int x,int p) {
		memset(vis,0,sizeof(int)*(n+10));
		vis[x]=1; Q.push(x);
		while (!Q.empty()) {
			int x=Q.front(); Q.pop();
			for (int i=fir[x];i;i=nex[i]) {
				if (high[i]>p&&!vis[arr[i]]) {
					vis[arr[i]]=1; Q.push(arr[i]);
				}
			}
		}
	}
	
	void doit() {
		int v,p; read(v); read(p);
		v=(v+k*lastans-1)%n+1;
		p=(p+k*lastans)%(s+1);
		bfs(v,p);
		LL ans=inf;
		for (int i=1;i<=n;i++) {
			if (vis[i]) ans=min(ans,dis[i]);
		}
		printf("%lld\n",ans);
		lastans=ans;
	}
	
	void Solve() {
		while (q--) doit();
	}
}

namespace Subtask2 {
	int fa[N];
	LL dx[N],ans[N];
	struct Query {
		int v,p,num;
	}que[N];

	bool cmp1(Query a,Query b) {
		return a.p>b.p;
	}

	bool cmp2(Eg a,Eg b) {
		return a.high>b.high;
	}

	inline int Find(int x) {
		return (fa[x]==x)?x:fa[x]=Find(fa[x]);
	}
	
	inline void Add(int x,int y) {
		int fx=Find(x),fy=Find(y);
		if (fx==fy) return;
		fa[fx]=fy; dx[fy]=min(dx[fy],dx[fx]);
	}
	
	void Solve() {
		for (int i=1;i<=n;i++) {
			fa[i]=i; dx[i]=dis[i];
		}
		for (int i=1;i<=q;i++) {
			int u,p;
			read(u); read(p);
			u=(u-1)%n+1; p=p%(s+1);
			que[i]=(Query){u,p,i};
		}
		sort(que+1,que+q+1,cmp1);
		sort(e+1,e+m+1,cmp2);
		int now=1;
		for (int i=1;i<=q;i++) {
			while (now<=m&&e[now].high>que[i].p) Add(e[now].x,e[now].y),now++;
			ans[que[i].num]=dx[Find(que[i].v)];
		}
		for (int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	}
}

void Solve() {
   read(n); read(m);
	E=0; memset(fir,0,sizeof(int)*(n+10));
	for (int i=1;i<=m;i++) {
		int x,y,l,h; read(x); read(y); read(l); read(h);
		Add_Edge(x,y,l,h); e[i]=(Eg){x,y,h};
	}
	Dijkstra();
	read(q); read(k); read(s);
	if (n<=2000) {
		Subtask1::Solve();
		return;
		}
	if (k==0) {
		Subtask2::Solve();
	}
}

int main() {
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	int T; read(T);
	while (T--) Solve();
	return 0;
}

评测结果