代码

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cctype>
#include <cassert>
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 write(int x){
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
namespace fastIO{
	const int SIZE=1e6;
	char buff[SIZE];
	char *l=buff,*r=buff;
	void init(){
		l=buff;
		r=l+fread(buff,1,SIZE,stdin);
	}
	char gc(){
		if (l==r) init();
		return *(l++);
	}
	void read(int &x){
		char ch=gc(); x=0;
		while (!isdigit(ch)) ch=gc();
		while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
	}
}
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]=2147483647;
	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){
			fastIO::read(v); fastIO::read(p);
			v=((long long)v+lastans-1)%n+1;
			p=((long long)p+lastans)%(s+1);
			write(lastans=bfs(v,p));
			putchar('\n');
		}
	}
}
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){
			fastIO::read(v[i]); fastIO::read(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){
			write(ans[i]);
			putchar('\n');
		}
	}
}
namespace Subtask3{
	#define M int mid=(l+r)>>1;
	#define L (st[ind].l,l,mid)
	#define R (st[ind].r,mid+1,r)
	int fa[N],sz[N],id[N<<1],root[N<<1],pos,now,v,p,tot,cp;
	struct node{
		int f,l,r;
	}st[N*60];//care
	bool cmp(int x,int y){
		return hei[x]>hei[y];
	}
	bool cmp2(int x,int y){
		return x>y;
	}
	int ask(int ind,int l,int r){
		if (l==r) return st[ind].f;
		M;
		return pos<=mid?ask L:ask R;
	}
	int finds(int x){
		pos=x;
		int t=ask(root[now],1,n);
//		cerr<<"fins"<<t<<endl;
		return t<=0?-t:finds(t);
	}
	int df(int v,int p){
		now=lower_bound(id+1,id+(k>>1)+1,p,cmp2)-id-1;
//		cerr<<"now"<<now<<endl;
		return finds(v);
	}
	void modify(int &ind,int l,int r){
//		if (tot+1==N*70) assert(0);
		st[ind=++tot]=st[cp];
//		cerr<<"modify"<<ind<<" "<<cp<<" "<<l<<" "<<r<<endl;
		if (l==r){
			st[ind].f=v;
			return;
		}
		M;
		pos<=mid?(cp=st[cp].l,modify L):(cp=st[cp].r,modify R);
	}
	int find(int x){
		return fa[x]<=0?x:find(fa[x]);
	}
	void fake(int x,int y,int i){
		x=find(x); y=find(y);
		if (x==y){
			root[i]=root[i-1];
			return;
		} 
		if (sz[x]<sz[y]) swap(x,y);
		fa[x]=max(fa[x],fa[y]);
		fa[y]=x;
		v=fa[y]; pos=y; cp=root[i-1];
		modify(root[i],1,n);
		v=fa[x]; pos=x; cp=root[i];
		modify(root[i],1,n);
		sz[x]+=sz[y];
//		for (int i=1; i<=n;++i) cerr<<fa[i]<<" ";
	}
	void build(int &ind,int l,int r){
		ind=++tot;
		if (l==r){
			st[ind].f=fa[l];
			return;
		}
		M;
		build L;
		build R;
	}
	void prework(){
		for (int i=1; i<=tot; ++i) st[i].f=st[i].l=st[i].r=0;
		tot=0;
		for (int i=1; i<=n; ++i){
			fa[i]=-f[i];
//			v=fa[i]; pos=i; cp=root[0];
//			modify(root[0],1,n);
			sz[i]=1;
		}
		build(root[0],1,n);
		for (int i=2; i<=k; i+=2) id[i>>1]=i;
		sort(id+1,id+(k>>1)+1,cmp);
		for (int i=1; i<=(k>>1); ++i) fake(b[id[i]],b[id[i]-1],i);
		for (int i=1; i<=(k>>1); ++i) id[i]=hei[id[i]];
	}
	void solve(){
		prework();
		int lastans=0;
		for (int i=1; i<=q; ++i){
			fastIO::read(v); fastIO::read(p);
			v=((long long)v+lastans-1)%n+1;
			p=((long long)p+lastans)%(s+1);
			write(lastans=df(v,p));
			putchar('\n');
		}
	}
}
int main(){
	freopen("return.in","r",stdin); 
	freopen("return.out","w",stdout);
	int t;
	fastIO::read(t);
	while (t--){
		fastIO::read(n); fastIO::read(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;
			fastIO::read(x); fastIO::read(y);
			fastIO::read(l); fastIO::read(a);
			add(x,y,l,a); add(y,x,l,a);
		}
		Dijkstra(1);
		int k;
		fastIO::read(q); fastIO::read(k); fastIO::read(s);
		
		if (k==1&&n>1500) Subtask3::solve();
		else if (k==1)  Subtask1::solve();
		else Subtask2::solve();
	}
} 

评测结果