代码

#include<cstdio>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define For(i, a, b) for(register int i = a; i <= b; ++ i)
#define FOR(i, a, b) for(register int i = a; i >= b; -- i)
#define go(x, i) for(register int i = head[x]; i; i = nxt[i])
#define PLI pair<ll, int>
#define mp make_pair

using namespace std;
typedef long long ll;

const int maxn = 400000 + 10;
int T, n, m;
int to[maxn << 1], head[maxn], nxt[maxn << 1], a[maxn << 1], l[maxn << 1], e;

template<class T>inline bool chkmin(T &_, T __)
{
	return _ > __ ? _ = __, 1 : 0;
}

template<class T>inline void read(T &_)
{
	T ___ = 1, __ = getchar();
	for(; !isdigit(__); __ = getchar()) if(__ == '-') ___ = -1;
	for(_ = 0; isdigit(__); __ = getchar()) _ = (_ << 3) + (_ << 1) + (__ ^ 48);
	_ *= ___;
}

void add(int x, int y, int L, int A)
{
	to[++ e] = y;
	nxt[e] = head[x];
	head[x] = e;
	l[e] = L;
	a[e] = A;
}

namespace Sub1
{
	ll dis[maxn];
	void Dijkstra()
	{
		__gnu_pbds::priority_queue<PLI, greater<PLI>, __gnu_pbds::pairing_heap_tag> q;
		For(i, 1, n)
			dis[i] = 1e18;
		q.push(mp(dis[1] = 0, 1));
		while(!q.empty())
		{
			PLI k = q.top(); q.pop();
			if(k.first > dis[k.second])
				continue;
			go(k.second, i)
				if(chkmin(dis[to[i]], dis[k.second] + l[i]))
					q.push(mp(dis[to[i]], to[i]));
		}
	}
	void solve()
	{
		int Q, K, s, x, y;
		Dijkstra();
		read(Q), read(K), read(s);
		For(cas, 1, Q)
		{
			scanf("%d%d", &x, &y);
			if(y == 0)
				puts("0");
			else
				printf("%lld\n", dis[x]);
		}
	}
}

namespace Sub2
{
	int fa[maxn][20], mnn[maxn][20], dep[maxn];
	ll len[maxn];
	void dfs(int x)
	{
		go(x, i)
			if(!dep[to[i]])
			{
				dep[to[i]] = dep[x] + 1;
				fa[to[i]][0] = x;
				mnn[to[i]][0] = a[i];
				len[to[i]] = len[x] + l[i];
				dfs(to[i]);	
			}
	}
	void solve()
	{
		For(i, 1, n)
			For(j, 0, 19)
				fa[i][j] = mnn[i][j] = 0;
		For(i, 1, n)
			len[i] = dep[i] = 0;
		ll lastans = 0;
		int Q, K, S, x, y;
		dfs(dep[1] = 1);
		For(j, 1, 19)
			For(i, 1, n)
			{
				fa[i][j] = fa[fa[i][j - 1]][j - 1];
				mnn[i][j] = min(mnn[i][j - 1], mnn[fa[i][j - 1]][j - 1]);
			}
		read(Q), read(K), read(S);
		while(Q --)
		{
			read(x), read(y);
			x = (lastans * K + x - 1) % n + 1;
			y = (lastans * K + y) % (S + 1);
			FOR(j, 19, 0)
				if(fa[x][j] != 0 && mnn[x][j] > y)
					x = fa[x][j];
			printf("%lld\n", lastans = len[x]);
		}
	}
}

int main()
{
	int x, y, L, A;
	for(read(T); T -- ; )
	{
		int flag = 0;
		read(n), read(m);
		For(i, 1, m)
		{
			read(x), read(y), read(L), read(A);
			add(x, y, L, A), add(y, x, L, A);
			flag += A;
		}
		if(flag == m)
			Sub1::solve();
		else if(m == n - 1)
			Sub2::solve();
		For(i, 1, e)
			head[i] = 0;
		e = 0;
	}
	return 0;
}

评测结果