代码

#include <bits/stdc++.h>
using namespace std;
const int N=200010,M=400010;
int ne[M<<1],k,fi[N],b[M<<1],c[M<<1],hei[M<<1];
int n,m,q,s,f[N];
void add(int x,int y,int l,int a){
	ne[++k]=fi[x]; b[fi[x]=k]=y; c[k]=l; hei[k]=a;
}
void Dijkstra(int s){
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	for (int i=1; i<=n; ++i) f[i]=INT_MAX;
	f[s]=0; pq.push(make_pair(f[s],s));
	while (!pq.empty()){
		int x=pq.top().second,y=pq.top().first; pq.pop();
		if (f[x]<y) continue;
		for (int j=fi[x]; j; j=ne[j])
		if (f[b[j]]>f[x]+c[j]){
			f[b[j]]=f[x]+c[j];
			pq.push(make_pair(f[b[j]],b[j]));
		}
	}
}
namespace Subtask1{
	bool in[N];
	int v,p;
	int bfs(int v,int p){
		for (int i=1; i<=n; ++i) in[i]=0;
		queue<int> q; q.push(v); in[v]=1;
		while (!q.empty()){
			int x=q.front(); q.pop();
			for (int j=fi[x]; j; j=ne[j])
			if (hei[j]>p&&!in[b[j]]){
				in[b[j]]=1;
				q.push(b[j]);
			}
		}
		int ret=f[v];
		for (int i=1; i<=n; ++i) if (in[i]) ret=min(ret,f[i]);
		return ret; 
	}
	void solve(){
		int lastans=0;
		for (int i=1; i<=q; ++i){
			scanf("%d%d",&v,&p);
			v=((long long)v+lastans-1)%n+1;
			p=((long long)p+lastans)%(s+1);
			printf("%d\n",(lastans=bfs(v,p)));
		}
	}
}
namespace Subtask2{
	int v[N],p[N],ans[N],id[N],id2[M],fa[N];
	bool cmp(int x,int y){
		return p[x]>p[y];
	}
	bool cmp2(int x,int y){
		return hei[x]>hei[y];
	}
	int ask(int x){
		return x==fa[x]?x:fa[x]=ask(fa[x]);
	}
	void unite(int x,int y){
		x=ask(x); y=ask(y);
		if (x==y) return;
		if (f[x]<f[y]) fa[y]=x;
		else fa[x]=y;
	}
	void solve(){
		for (int i=1; i<=q; ++i){
			scanf("%d%d",&v[i],&p[i]);
			id[i]=i;
		}
		sort(id+1,id+q+1,cmp);
		for (int i=2; i<=k; i+=2) id2[i>>1]=i;
		sort(id2+1,id2+(k>>1)+1,cmp2);
		int ne=1;
		for (int i=1; i<=n; ++i) fa[i]=i;
		for (int i=1; i<=q; ++i){
			while (ne<=k>>1&&hei[id2[ne]]>p[id[i]]){
				unite(b[id2[ne]],b[id2[ne]-1]);
				++ne;
			}
			ans[id[i]]=f[ask(v[id[i]])];
		}
		for (int i=1; i<=q; ++i) printf("%d\n",ans[i]);
	}
}
int main(){
	freopen("return.in","r",stdin);freopen("return.out","w",stdout);
	int t;
	scanf("%d",&t);
	while (t--){
		scanf("%d%d",&n,&m);
		for (int i=1; i<=n; ++i) fi[i]=0; k=0;
		for (int i=1; i<=m; ++i){
			int x,y,l,a;
			scanf("%d%d%d%d",&x,&y,&l,&a);
			add(x,y,l,a); add(y,x,l,a);
		}
		Dijkstra(1);
		int k;
		scanf("%d%d%d",&q,&k,&s);
		
		if (k==1) Subtask1::solve();
		else Subtask2::solve();
	}
} 

评测结果