代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Edge {
	int i, j;
	int w;
	int h;
	
	Edge(int i, int j, int w, int h)
		: i(i), j(j), w(w), h(h) {}
};

bool edge_bigger_h(Edge a, Edge b)
{ return a.h > b.h; }

struct Path {
	int j;
	int w;
	int h;
	
	Path(int j, int w, int h)
		: j(j), w(w), h(h) {}
};

vector<Path> path_of[200005];
int N;

int dis[200005];
void spfa()
{
	fill(&dis[1], &dis[N]+1, 1e8);
	dis[1] = 0;
	
	queue<int> Q;
	Q.push(1);
	
	while(! Q.empty()) {
		int i = Q.front();
		Q.pop();
		
		for(int pathi = 0; pathi < path_of[i].size(); pathi++) {
			int j = path_of[i][pathi].j;
			int w = path_of[i][pathi].w;
			
			if(dis[j] > dis[i] + w) {
				dis[j] = dis[i] + w;
				Q.push(j);
			}
		}
	}
}

class Union_Find_Set {
private:
	int ufs[200005];
	int minimal[200005];
	
	int root_of(int i)
	{
		if(ufs[i] == i)
			return i;
		else
			return ufs[i] = root_of(ufs[i]);
	}
	
public:
	Union_Find_Set(int N)
	{
		for(int i = 1; i <= N; i++) {
			ufs[i] = i;
			minimal[i] = dis[i];
		}
	}
	
	void merge(int i, int j)
	{
		minimal[root_of(j)] = min(minimal[root_of(i)], minimal[root_of(j)]);
		ufs[root_of(i)] = root_of(j);
	}
	
	bool in_same_set(int i, int j)
	{ return root_of(i) == root_of(j); }
	
	int min_in(int i)
	{ return minimal[root_of(i)]; }
};

struct Query {
	int e;
	int h;
	int id;
	
	Query(int e, int h, int id)
		: e(e), h(h), id(id) {}
};

bool query_bigger_h(Query a, Query b)
{ return a.h > b.h; }

bool C[1501];
void color_C(int i, int h)
{
	fill(&C[1], &C[N]+1, false);
	C[i] = true;
	
	queue<int> Q;
	Q.push(i);
	
	while(! Q.empty()) {
		int i = Q.front();
		Q.pop();
		
		for(int pathi = 0; pathi < path_of[i].size(); pathi++) {
			int j = path_of[i][pathi].j;
			int h2 = path_of[i][pathi].h;
			
			if(! C[j] && h2 > h) {
				C[j] = true;
				Q.push(j);
			}
		}
	}
}

bool is_tree()
{
	for(int i = 1; i <= N; i++)
		if(path_of[i].empty())
			return false;
	
	return true;
}

int depth[200005];
int st[200005][20];
int min_h[200005][20];
void get_st(int i)
{
	static bool vis[200005];
	
	vis[i] = true;
	
	for(int pathi = 0; pathi < path_of[i].size(); pathi++) {
		int j = path_of[i][pathi].j;
		int h = path_of[i][pathi].h;
		
		if(! vis[j]) {
			depth[j] = depth[i] + 1;
			st[j][0] = i;
			min_h[j][0] = h;
			get_st(j);
		}
	}
}

int main()
{
	int T;
	cin >> T;
	
	while(T--) {
		int M;
		cin >> N >> M;
		
		vector<Edge> edges;
		while(M--) {
			int i, j, w, h;
			cin >> i >> j >> w >> h;
			
			edges.push_back(Edge(i,j,w,h));
			path_of[i].push_back(Path(j,w,h));
			path_of[j].push_back(Path(i,w,h));
		}
		sort(edges.begin(), edges.end(), edge_bigger_h);
		spfa();
		
		int QN, K, S;
		cin >> QN >> K >> S;
		
		if(K == 0) {
			vector<Query> Q;
			for(int id = 1; id <= QN; id++) {
				int e, h;
				cin >> e >> h;
				
				Q.push_back(Query(e, h, id));
			}
			sort(Q.begin(), Q.end(), query_bigger_h);
			
			Union_Find_Set ufs(N);
			static int ans[200005];
			int i = 0;
			for(int qi = 0; qi < Q.size(); qi++) {
				Query q = Q[qi];
				
				while(i+1 < edges.size() && edges[i].h > q.h) {
					ufs.merge(edges[i].i, edges[i].j);
					i++;
				}
				
				ans[q.id] = ufs.min_in(q.e);
			}
			
			for(int i = 1; i <= QN; i++)
				cout << ans[i] << endl;
		}
		
		else if(N == M+1 && is_tree()) {
			get_st(1);
			for(int i = 1; i <= N; i++)
			for(int k = 1; 1<<k <= depth[i]; k++) {
				st[i][k] = st[st[i][k-1]][k-1];
				min_h[i][k] = min(min_h[i][k-1], min_h[st[i][k-1]][k-1]);
			}
			
			int last_ans = 0;
			while(QN--) {
				int i, h;
				cin >> i >> h;
				i = (i + last_ans - 1) % N + 1;
				h = (h + last_ans) % (S+1);
				
				for(int k = log2(depth[i]); k >= 0; k--)
					if(min_h[i][k] > h)
						i = st[i][k];
				
				cout << dis[i] << endl;
			}
		}
		
		else {
			int last_ans = 0;
			while(QN--) {
				int i, h;
				cin >> i >> h;
				i = (i + last_ans - 1) % N + 1;
				h = (h + last_ans) % (S+1);
				
				color_C(i,h);
				last_ans = 1e8;
				for(int i = 1; i <= N; i++)
					if(C[i])
						last_ans = min(last_ans, dis[i]);
				
				cout << last_ans << endl;
			}
		}
	}
}

评测结果