代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N=600000,M=1200000;
int n,m,tot,Next[M],head[N],tree[M],val[M],height[M],a[N],V[N],f[N],dis[N],Min[N],fa[N][22],F[N][22];
bool vis[N];
struct Edge{int u,v,l,x;}E[M];
vector<int>P[N];

struct Node
{
  int d, n;
} cur;
struct cmp
{
  bool operator()(Node a, Node b) { return a.d > b.d; }
};
priority_queue<Node, vector<Node>, cmp> Q;

void add(int x,int y,int l,int X)
{
	tot++;
	Next[tot]=head[x];
	head[x]=tot;
	tree[tot]=y;
	val[tot]=l;
	height[tot]=X;
}
void Dijkstra()
{
	for (int i=1;i<=n;i++) dis[i]=1<<29,vis[i]=0;
	cur.d = 0;
    cur.n = 1;
    Q.push(cur);
    dis[1] = 0;
    while (!Q.empty())
    {
        int u = Q.top().n;
        Q.pop();
        if (vis[u])
        continue;
        vis[u] = true;
        for (int i = head[u]; i; i = Next[i])
        {
            int v = tree[i];
            if (!vis[v] && dis[v] > dis[u] + val[i])
            {
                dis[v] = dis[u] + val[i];
                cur.d = dis[v];
                cur.n = v;
                Q.push(cur);
            }
        }
    }
}
bool cmp(Edge a,Edge b) { return a.x>b.x;}
int get(int x)
{
	if (f[x]==x) return x;else f[x]=get(f[x]);
	return f[x];
}
void dfs(int u,int father)
{
	Min[u]=dis[u];
	F[u][0]=V[father];
	fa[u][0]=father;
	for (int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for (int i=1;i<=20;i++) F[u][i]=min(F[u][i-1],F[fa[u][i-1]][i-1]);
	for (int i=0;i<P[u].size();i++)
	{
		int v=P[u][i];
		if (v==father) continue;
		dfs(v,u);
		Min[u]=min(Min[u],Min[v]);
	}
}
int get_ans(int u,int X)
{
	for (int i=20;i>=0;i--)
		if (F[u][i]>=X) u=fa[u][i];
	return u;
}
int main()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d",&n,&m);
        tot=0;
        memset(head,0,sizeof(head));
		for (int i=1;i<=m;i++)
		{
			int u,v,l,x;
			scanf("%d%d%d%d",&u,&v,&l,&x);
			add(u,v,l,x);add(v,u,l,x);
			E[i]=(Edge){u,v,l,x};
		}
		for (int i=1;i<=n;i++) V[i]=1<<30;
		Dijkstra();
		sort(E+1,E+m+1,cmp);
		for (int i=1;i<=n;i++) f[i]=i;
		int cnt=n;
		for (int i=1;i<=m;i++)
		{
			int u=E[i].u,v=E[i].v,u1=get(u),v1=get(v);
			if (u1!=v1)
			{
				V[++cnt]=E[i].x;
				f[cnt]=cnt;
				dis[cnt]=1<<29;
				P[cnt].push_back(u1);
				P[cnt].push_back(v1);
				f[u1]=f[v1]=cnt;
			}
		}
		int root=0;
		for (int i=1;i<=cnt;i++)
			if (get(i)==i) { root=i;break;}
		for (int i=0;i<=cnt;i++)
			for (int j=0;j<=20;j++) F[i][j]=1<<30,fa[i][j]=0;
		dfs(root,0);
		int Q,K,S;
		scanf("%d%d%d",&Q,&K,&S);
		int lastans=0;
		while (Q--)
		{
			int v0,p0;
			scanf("%d%d",&v0,&p0);
			v0=(v0+K*lastans-1)%n+1;
			p0=(p0+K*lastans)%(S+1);
			lastans=Min[get_ans(v0,p0+1)];
			printf("%d\n",lastans);
		}
        for (int i=1;i<=cnt;i++) P[i].clear();
	}
	return 0;
}

评测结果