代码

#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<cstring>
#include<set>
#include<algorithm>
#include<cmath>
#define MAXN 200005
#define MAXM 400005
#define LL long long
#define INF (1ll<<45)

using namespace std;


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){}
	
	bool operator < (const Edge& e1) const {
		return a > e1.a;
	}
} eList[MAXM];

vector<Edge> Adj[MAXN];
int T,N,M;
int Q,K,S;
struct Node{
	int id;
	LL d;
	Node(int id=0, LL d=0):id(id), d(d){}
	
	bool operator <(const Node& n1) const{
		return d > n1.d;
	}
};

struct Query{
	int v0, p0;
	int id;
	
	Query(int id=0, int v0=0, int p0=0):id(id),v0(v0),p0(p0){}
	
	bool operator < (const Query& q1) const{
		return p0 > q1.p0;
	}
} qList[MAXM];
LL ans[MAXM];

LL d[MAXN];
void dijkstra(int a0){
	priority_queue<Node> q;
	for(int i=1;i<=N;i++) d[i] = INF;
	d[1] = 0;
	q.push(Node(1,0));
	
	int u,v,a;
	LL w;
	while(!q.empty()){
		Node cur = q.top(); q.pop();
		u = cur.id;
		//cout<<"u: "<<u<<endl;
		for(int k=0;k<Adj[u].size();k++){
			v = Adj[u][k].v;
			w = Adj[u][k].l;
			a = Adj[u][k].a;
			if(a <= a0) continue;
			//cout<<d[u]+w<<" "<<v<<" "<<d[v]<<endl;
			if(d[u] + w < d[v]){
				d[v] = d[u] + w;
				q.push(Node(v, d[v]));
			}
		}
	}
}


int p[MAXN]; LL minD[MAXN];
int findR(int x){
	if(p[x]==x) return x;
	else return p[x] = findR(p[x]);
}
void solve0(){
	//cout<<"solve0"<<endl;
	dijkstra(0);
	
	sort(eList+1, eList+1+M);
	for(int i=1;i<=N;i++){
		p[i] = i;
		minD[i] = d[i];
		//cout<<d[i]<<" ";
	}
	
	
	sort(qList+1, qList+1+Q);
	//sort(eList+1, eList+1+M);
	int v0,p0,id;
	
	int p1 = 0;
	for(int i=1;i<=Q;i++){
		id = qList[i].id;
		v0 = qList[i].v0;
		p0 = qList[i].p0;
		
		int u,v,ru,rv;
		while(p1==0 || (p1<=M && eList[p1].a>p0)){
			u = eList[p1].u;
			v = eList[p1].v;
			p1++;
			ru = findR(u);
			rv = findR(v);
			if(ru == rv) continue;
			p[ru] = rv;
			minD[rv] = min(minD[rv], minD[ru]);	
		}
		
		ans[id] = minD[findR(v0)];
	}
	
	for(int i=1;i<=Q;i++) printf("%lld\n", ans[i]);
	return;
}

LL work(int v0, int p0);
void solve1(){
	
	dijkstra(0);
	int v0, p0;
	LL last = 0;
	for(int i=1;i<=Q;i++){
		v0 = (qList[i].v0 + last - 1)%N + 1;
		p0 = (qList[i].p0 + last)%(S+1);
		
		last = work(v0, p0);
	}
}

LL work(int v0, int p0){
	//cout<<"work: "<<v0<<" "<<p0<<endl;
	
	for(int i=1;i<=N;i++){
		p[i] = i;
		minD[i] = d[i];
	}
	
	sort(eList+1, eList+1+M);
	int u,v,ru,rv;
	for(int i=1;i<=M;i++){
		if(eList[i].a <= p0) break;
		u = eList[i].u;
		v = eList[i].v;
		ru = findR(u);
		rv = findR(v);
		if(ru == rv) continue;
		p[ru] = rv;
		minD[rv] = min(minD[rv], minD[ru]);
	}
	printf("%lld\n", minD[findR(v0)]);
	return minD[findR(v0)];
}

void init();

int main(){
		
//	freopen("return4.in", "r", stdin);
//	freopen("return4.out", "w", stdout);
	
	cin>>T;
	while(T--){
		scanf("%d%d", &N, &M);
		init();
		int u,v,l,a;
		for(int i=1;i<=M;i++){
			scanf("%d %d %d %d", &u, &v, &l, &a);
			//cout<<u<<" "<<v<<" "<<l<<" "<<a<<endl;
			eList[i] = Edge(u,v,l,a);
			Adj[u].push_back(Edge(u,v,l,a));
			Adj[v].push_back(Edge(v,u,l,a));
		}
		
		scanf("%d%d%d", &Q, &K, &S);
		
		int v0,p0;
		for(int i=1;i<=Q;i++){
			scanf("%d%d", &v0, &p0);
			qList[i] = Query(i, v0, p0);
		}
		
		if(K == 0) solve0();
		else solve1();
	}
	
	return 0;
}


void init(){
	for(int i=1;i<=N;i++) Adj[i].clear();
}

评测结果