代码

#define _CRT_SECURE_NO_DEPRECATE
/************************
*创建时间：2018 10 09
*文件类型：源代码文件
*题目来源：洛谷
*当前状态：已通过
*备忘录：图论 最小生成树 kruskal重构树
*作者：HtBest
************************/
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <bitset>
// #include <sys/wait.h>
// #include <sys/types.h>
// #include <unistd.h>
using namespace std;
#define MAXN 200001
#define MAXM 400001
int n,m,q,k,s,_edge,head[MAXN],d[MAXN],//基本
son[2*MAXN],fa[2*MAXN],bro[2*MAXN],h[2*MAXN],f[2*MAXN],_node,//kruskal重构树
mind[2*MAXN],up[2*MAXN][20];//统计答案
struct EDGE 
{
	int a,b,v,h,next;
	EDGE(int a=0,int b=0,int v=0,int h=0,int next=0):a(a),b(b),v(v),h(h),next(next){}
	bool operator < (EDGE x) const 
	{
		return h>x.h;
	}
}edge[2*MAXM];
struct A 
{
	int id,d;
	A(int id=0,int d=0):id(id),d(d){}
	bool operator < (A x) const 
	{
		return d>x.d;
	}
};
/* Variable explain:
n:节点数
m:边数
q:询问数
edge[i]:邻接表
_edge:邻接表标记
h[i]:kruskal重构树上第i个点的海拔
_node:节点标记
f[i]:并查集
son[i]:i的子节点
fa[i]:i的父亲
bro[i]:i的下一个兄弟
*/
void adde(int a,int b,int v,int h)
{
	edge[++_edge]=EDGE(a,b,v,h,head[a]);
	head[a]=_edge;
}
void addt(int a,int b)
{
	// printf("%d<--%d\n",a,b);
	fa[b]=a;
	bro[b]=son[a];
	son[a]=b;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int a,int b){f[find(a)]=find(b);}
void read()
{
	int ls1,ls2,ls3,ls4;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)head[i]=0,h[i]=1e9;
	for(int i=1;i<=2*n;++i)son[i]=fa[i]=bro[i]=0,mind[i]=1e9;
	_edge=0;_node=n;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d%d",&ls1,&ls2,&ls3,&ls4),adde(ls1,ls2,ls3,ls4),adde(ls2,ls1,ls3,ls4);
	}
	scanf("%d%d%d",&q,&k,&s);
	return;
}
void kruskal()
{
	sort(edge+1,edge+1+_edge);
	for(int i=1;i<=2*n;++i)f[i]=i;
	for(int i=1;i<=_edge;++i)
	{
		int a=edge[i].a,b=edge[i].b;
		if(find(a)!=find(b))
		{
			addt(++_node,find(a));
			addt(_node,find(b));
			h[_node]=edge[i].h;
			merge(a,_node);
			merge(b,_node);
		}
	}
}
void dijkstra()
{
	bitset <MAXN> vis;
	priority_queue <A> q;
	q.push(A(1,0));
	for(int i=1;i<=n;++i)d[i]=1e9;
	d[1]=0;
	while(!q.empty())
	{
		int a=q.top().id;
		q.pop();
		if(vis[a])continue;
		vis[a]=true;
		for(int i=head[a];i;i=edge[i].next)
		{
			int b=edge[i].b,v=edge[i].v;
			if(d[b]>d[a]+v)
			{
				d[b]=d[a]+v;
				q.push(A(b,d[b]));
			}
		}
	}
}
void dfs(int a)
{
	for(int i=son[a];i;i=bro[i])
	{
		dfs(i);
		mind[a]=min(mind[a],mind[i]);
		// printf("%d(%d) --> %d\n",i,mind[i],a);
	}
	if(a<=n)mind[a]=d[a];
}
void init()
{
	for(int i=1;i<=_node;++i)up[i][0]=fa[i];
	for(int j=1;j<20;++j)
		for(int i=1;i<=_node;++i)up[i][j]=up[up[i][j-1]][j-1];
}
int solve(int S,int H)
{
	for(int i=19;i>=0;--i)
	{
		if(h[up[S][i]]>H)S=up[S][i];
	}
	return S;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		read();
		dijkstra();
		kruskal();
		dfs(_node);
		init();
		int ans=0;
		while(q--)
		{
			int S,H;
			scanf("%d%d",&S,&H);
			S=(S+k*ans-1)%n+1;
			H=(H+k*ans)%(s+1);
			// printf("Q:%d %d\n",S,H);
			S=solve(S,H);
			printf("%d\n",ans=mind[S]);
			// printf("%d %d\n",S,ans=mind[S]);
		}
	}
	
	return 0;
}

评测结果