代码

#include <bits/stdc++.h>
using namespace std;
#define mkpr make_pair
#define ft first
#define sd second

typedef long long LL;
typedef pair<int, int> PII;
const int MAXN=200011, MAXM=400011;
struct edge {
	int x, y, l, h, nxt;
} E[MAXM<<1];
int head[MAXN], vis[MAXN], fa[MAXN], eid[MAXM];
LL dis[MAXN];
int n, m, q, k, s, tot;
priority_queue<PII, vector<PII>, greater<PII> > Q;

inline void addedge(int x, int y, int l, int h) {
	E[++tot]=(edge){x, y, l, h, head[x]};
	head[x]=tot;
}

inline void Dijkstra() {
	memset(dis, 0x7f, sizeof dis);
	memset(vis, 0, sizeof vis);
	while(!Q.empty()) Q.pop();
	Q.push(mkpr(0, 1));
	dis[1]=0;
	while(!Q.empty()) {
		PII now=Q.top(); Q.pop();
		if(vis[now.sd]) continue;
		vis[now.sd]=1;
		for(int i=head[now.sd];~i;i=E[i].nxt) {
			int to=E[i].y;
			if(dis[to]>dis[now.sd]+E[i].l) {
				dis[to]=dis[now.sd]+E[i].l;
				if(!vis[to]) Q.push(mkpr(dis[to], to));
			}
		}
	}
}

struct queries {
	int v, p, id;
} ques[MAXM];
LL mnd[MAXN], ans[MAXM];

inline bool cmp(queries a, queries b) {
	return a.p!=b.p ? a.p>b.p : a.v<b.v;
}

inline bool cmp2(int a, int b) {
	return E[a].h!=E[b].h ? E[a].h>E[b].h : E[a].l<E[b].l;
}

inline int getfa(int x) {
	if(fa[x]==x) return x;
	else {
		fa[x]=getfa(fa[x]);
		mnd[x]=mnd[x]<=mnd[fa[x]] ? mnd[x] : mnd[fa[x]];
		return fa[x];
	}
}

inline void Solve() {
	for(int i=1;i<=q;++i) {
		scanf("%d%d", &ques[i].v, &ques[i].p);
		ques[i].id=i;
	}
	sort(ques+1, ques+1+q, cmp);
	for(int i=1;i<=n;++i) {
		fa[i]=i;
		mnd[i]=dis[i];
	}
	sort(eid+1,eid+1+m, cmp2);
	int pnt=1;
	for(int i=1;i<=q;++i) {
		while(pnt<=m && E[eid[pnt]].h>ques[i].p) {
			int x=E[eid[pnt]].x, y=E[eid[pnt]].y;
			int fx=getfa(x), fy=getfa(y);
			if(fx!=fy) {
				fa[fx]=fy;
				mnd[fy]=min(mnd[fy], mnd[fx]);
				mnd[fx]=min(mnd[fx], mnd[fy]);
				mnd[fy]=min(mnd[y], mnd[x]);
				mnd[fx]=min(mnd[x], mnd[y]);
				mnd[x]=min(mnd[x], mnd[y]);
				mnd[y]=min(mnd[x], mnd[y]);
			}
			++pnt;
		}
		int pos=getfa(ques[i].v);
		ans[ques[i].id]=mnd[pos];
	}
	for(int i=1;i<=q;++i) {
		printf("%lld\n", ans[i]);
	}
}

inline void Solve2() {
	LL lastans=0;
	for(int i=1, qv, qp;i<=q;++i) {
		for(int j=1;j<=n;++j) {
			fa[j]=j;
			mnd[j]=dis[j];
		}
		scanf("%d%d", &qv, &qp);
		qv=(qv-1+lastans)%n+1;
		qp=(qp+lastans)%(s+1);
		for(int j=1;j<=m;++j) {
			if(E[eid[j]].h<=qp) continue;
			int x=E[eid[j]].x, y=E[eid[j]].y;
			int fx=getfa(x), fy=getfa(y);
			if(fx!=fy) {
				fa[fx]=fy;
				mnd[fy]=min(mnd[fy], mnd[fx]);
				mnd[fx]=min(mnd[fx], mnd[fy]);
				mnd[fy]=min(mnd[y], mnd[x]);
				mnd[fx]=min(mnd[x], mnd[y]);
				mnd[x]=min(mnd[x], mnd[y]);
				mnd[y]=min(mnd[x], mnd[y]);
			}
		}
		int pos=getfa(qv);
		printf("%lld\n", mnd[pos]);
		lastans=mnd[pos];
	}
}

int main() {
	freopen("return.in", "r", stdin);
	freopen("return.out", "w", stdout);
	int T;
	scanf("%d", &T);
	while(T--) {
		memset(head, -1, sizeof head);
		tot=0;
		scanf("%d%d", &n, &m);
		for(int i=1, w, x, y, z;i<=m;++i) {
			scanf("%d%d%d%d", &w, &x, &y, &z);
			addedge(w, x, y, z);
			eid[i]=tot;
			addedge(x, w, y, z);
		}
		Dijkstra();
		scanf("%d%d%d", &q, &k, &s);
		if(k==0) Solve();
		else Solve2();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

评测结果