代码

// Problem: P4768 [NOI2018] 归程
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4768
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
// #define int long long
#define min(x,y) (((x)<(y))?(x):(y))
#define max(x,y) (((x)>(y))?(x):(y))
#define lowbit(x) ((x)&-(x))
#define abs(x) (((x)<(0))?(-(x)):(x))
#define swap(a,b) a^=b^=a^=b
#define INF 1e18
#define MAXN 1200005
using namespace std;
struct EDGE
{
	int u, v, l, h;
} edge[MAXN];
int T, n, m, lastans, q, k, s, v, p, cnt, dis[MAXN], mindis[MAXN], ufs[MAXN];
int fa[MAXN], ls[MAXN], rs[MAXN], anck[MAXN], rodeh[MAXN], rodeid[MAXN], anc[MAXN][21];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;
vector<pair<int,int> > e[MAXN];
bool cmph(EDGE a, EDGE b)
{
	return a.h < b.h;
}
int getfa(int id)
{
	if (ufs[id] == id)
	{
		return id;
	}
	return ufs[id] = getfa(ufs[id]);
}
void dfsanc(int id)
{
	anc[id][0] = fa[id];
	for (int i = 1; i <= 20 && anc[id][i - 1] != 0; i++)
	{
		anc[id][i] = anc[anc[id][i - 1]][i - 1];
	}
	if (id <= n)
	{
		return;
	}
	dfsanc(ls[id]);
	dfsanc(rs[id]);
}
signed main()
{
	cin >> T;
	while (T--)
	{
		lastans = 0;
		cnt = 0;
		for (int i = 0; i < MAXN; i++)
		{
			e[i].clear();
		}
		memset(dis, 0x3f, sizeof(dis));
		memset(mindis, 0x3f, sizeof(mindis));
		memset(rodeh, -2, sizeof(rodeh));
		memset(rodeid, 0, sizeof(rodeid));
		memset(fa, 0, sizeof(fa));
		memset(ls, 0, sizeof(ls));
		memset(rs, 0, sizeof(rs));
		memset(ufs, 0, sizeof(ufs));
		memset(anck, 0, sizeof(anck));
		memset(edge, 0, sizeof(edge));
		memset(anc, 0, sizeof(anc));
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
		{
			ufs[i] = i;
			anck[i] = i;
			rodeh[i] = INF;
		}
		for (int i = 1; i <= m; i++)
		{
			cin >> edge[i].u >> edge[i].v >> edge[i].l >> edge[i].h;
			e[edge[i].u].push_back({edge[i].v, edge[i].l});
			e[edge[i].v].push_back({edge[i].u, edge[i].l});
		}
		dis[1] = 0;
		que.push({0, 1});
		while (!que.empty())
		{
			pair<int,int> t = que.top();
			que.pop();
			if (t.first != dis[t.second])
			{
				continue;
			}
			for (pair<int,int> i : e[t.second])
			{
				if (dis[i.first] > t.first + i.second)
				{
					dis[i.first] = t.first + i.second;
					que.push({dis[i.first], i.first});
				}
			}
		}
		for (int i = 1; i <= n; i++)
		{
			mindis[i] = dis[i];
			// cout << dis[i] << " ";
		}
		// cout << endl;
		sort(edge + 1, edge + m + 1, cmph);
		for (int i = m; i >= 1; i--)
		{
			if (getfa(edge[i].u) != getfa(edge[i].v))
			{
				// cout << edge[i].u << " " << edge[i].v << "  ";
				// cout << getfa(edge[i].u) << " " << getfa(edge[i].v) << "  ";
				// cout << anck[getfa(edge[i].u)] << " " << anck[getfa(edge[i].v)] << "\n";
				// cout << "fa:\t";
				// for (int i = 1; i <= n + n - 1; i++)
				// {
					// cout << fa[i] << " ";
				// }
				// cout << endl;
				// cout << "ls:\t";
				// for (int i = 1; i <= n + n - 1; i++)
				// {
					// cout << ls[i] << " ";
				// }
				// cout << endl;
				// cout << "rs:\t";
				// for (int i = 1; i <= n + n - 1; i++)
				// {
					// cout << rs[i] << " ";
				// }
				// cout << endl;
				// cout << "rodeid:\t";
				// for (int i = 1; i <= n + n - 1; i++)
				// {
					// cout << rodeid[i] << " ";
				// }
				// cout << endl;
				// cout << "mindis:\t";
				// for (int i = 1; i <= n + n - 1; i++)
				// {
					// cout << mindis[i] << " ";
				// }
				// cout << endl;
				cnt++;
				fa[anck[getfa(edge[i].u)]] = n + cnt;
				fa[anck[getfa(edge[i].v)]] = n + cnt;
				ls[n + cnt] = anck[getfa(edge[i].u)];
				rs[n + cnt] = anck[getfa(edge[i].v)];
				rodeh[n + cnt] = edge[i].h;
				rodeid[n + cnt] = i;
				mindis[n + cnt] = min(mindis[anck[getfa(edge[i].u)]], mindis[anck[getfa(edge[i].v)]]);
				anck[getfa(edge[i].v)] = n + cnt;
				ufs[getfa(edge[i].u)] = getfa(edge[i].v);
				// cout << edge[i].u << " " << edge[i].v << "  ";
				// cout << getfa(edge[i].u) << " " << getfa(edge[i].v) << "  ";
				// cout << anck[getfa(edge[i].u)] << " " << anck[getfa(edge[i].v)] << "\n";
				// cout << "fa:\t";
				// for (int i = 1; i <= n + n - 1; i++)
				// {
					// cout << fa[i] << " ";
				// }
				// cout << endl;
				// cout << "ls:\t";
				// for (int i = 1; i <= n + n - 1; i++)
				// {
					// cout << ls[i] << " ";
				// }
				// cout << endl;
				// cout << "rs:\t";
				// for (int i = 1; i <= n + n - 1; i++)
				// {
					// cout << rs[i] << " ";
				// }
				// cout << endl;
				// cout << "rodeid:\t";
				// for (int i = 1; i <= n + n - 1; i++)
				// {
					// cout << rodeid[i] << " ";
				// }
				// cout << endl;
				// cout << "mindis:\t";
				// for (int i = 1; i <= n + n - 1; i++)
				// {
					// cout << mindis[i] << " ";
				// }
				// cout << endl;
				// cout << endl;
				// cout << endl;
			}
		}
		// cout << "fa:\t";
		// for (int i = 1; i <= n + n - 1; i++)
		// {
			// cout << fa[i] << " ";
		// }
		// cout << endl;
		// cout << "ls:\t";
		// for (int i = 1; i <= n + n - 1; i++)
		// {
			// cout << ls[i] << " ";
		// }
		// cout << endl;
		// cout << "rs:\t";
		// for (int i = 1; i <= n + n - 1; i++)
		// {
			// cout << rs[i] << " ";
		// }
		// cout << endl;
		// cout << "rodeid:\t";
		// for (int i = 1; i <= n + n - 1; i++)
		// {
			// cout << rodeid[i] << " ";
		// }
		// cout << endl;
		// cout << "mindis:\t";
		// for (int i = 1; i <= n + n - 1; i++)
		// {
			// cout << mindis[i] << " ";
		// }
		// cout << endl;
		// cout << "rodeh:\t";
		// for (int i = 1; i <= n + n - 1; i++)
		// {
			// cout << rodeh[i] << " ";
		// }
		// cout << endl;
		dfsanc(n + n - 1);
		cin >> q >> k >> s;
		for (int i = 1; i <= q; i++)
		{
			cin >> v >> p;
			v = (v + lastans * k - 1) % n + 1;
			p = (p + lastans * k) % (s + 1);
			// cout << v << " " << p << endl;
			for (int i = 20; i >= 0; i--)
			{
				while (rodeh[anc[v][i]] > p)
				{
					v = anc[v][i];
				}
			}
			// cout << v << " " << rodeh[v] << " " << fa[v] << " " << rodeh[fa[v]] << " ";
			cout << mindis[v] << endl;
			lastans = mindis[v];
		}
	}
	return 0;
}

评测结果