代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define fo(i,a,b) for (i=a; i<=b; i++)
using namespace std;

const int N=200005, M=400005, W=18;
int t0, n, m, q, k0, s, i, j, x, y, t1, t2, t, lans, ans;
int lst[N], e[M*2][4];
int f[N], d[N], h[N];
int fa[N][W+1], g[N][W+1];
bool bz[N];
bool flag, flag2;
struct que{int x, h, i;}c[N];
struct map{int x, y, h;}c2[N];

void link(int x,int y)
{
	e[++t][0]=lst[x], e[t][1]=y, e[t][2]=t1, e[t][3]=t2, lst[x]=t;
}

void up(int x)
{
	int y=x>>1;
	while (y && f[d[x]]<f[d[y]])
	{
		swap(d[x],d[y]), h[d[x]]=x, h[d[y]]=y;
		x=y, y=x>>1;
	}
}
void down()
{
	int x=1, y=2;
	while ((y<=t && f[d[x]]>f[d[y]]) || (y<t && f[d[x]]>f[d[y+1]]))
	{
		if (y<t && f[d[y+1]]<f[d[y]]) y++;
		swap(d[x],d[y]), h[d[x]]=x, h[d[y]]=y;
		x=y, y=x<<1;
	}
}
void spfa()
{
	t=d[1]=h[1]=1;
	memset(f,120,sizeof(f)), f[1]=0; int w0=f[2]; 
	memset(bz,0,sizeof(bz));
	while (t)
	{
		int x=d[1], i=lst[x]; bz[x]=1; 
		while (i)
		{
			int y=e[i][1]; 
			if (!bz[y] && f[x]+e[i][2]<f[y])
			{
				bool flag=(f[y]==w0); f[y]=f[x]+e[i][2];
				if (flag) h[y]=++t, d[t]=y, up(t); else up(h[y]);
			}
			i=e[i][0];
		}
		h[x]=0, h[d[t]]=1, d[1]=d[t], t--, down();
	}
}
void build(int x)
{
	int i=lst[x];
	while (i)
	{
		int y=e[i][1];
		if (fa[x][0]!=y)
		{
			fa[y][0]=x, g[y][0]=e[i][3], f[y]=f[x]+e[i][2], build(y);
		}
	}
}

bool cmp(que a,que b) {return a.h>b.h;}
bool cmp2(map a,map b) {return a.h>b.h;}

int find(int x)
{
	if (h[x]==x) return x;
	return h[x]=find(h[x]);
}
void merge(int x,int y)
{
	x=find(x), y=find(y), h[x]=y, f[y]=min(f[x],f[y]);
}

int main()
{
	scanf("%d",&t0);
	while (t0)
	{
		memset(lst,0,sizeof(lst)), t=lans=0;
		t0--, scanf("%d%d",&n,&m), flag=flag2=1;
		fo(i,1,m) 
		{
			scanf("%d%d%d%d",&x,&y,&t1,&t2), link(x,y), link(y,x);
			if (t2>1) flag=0;  if (x+1!=y) flag2=0;
		}
		scanf("%d%d%d",&q,&k0,&s);
		if (flag)
		{
			spfa(); //
			fo(i,1,q)
			{
				scanf("%d%d",&x,&y);
				if (!y) printf("0\n"); else printf("%d\n",f[x]);
			}
		}
		else
		if (m==n-1)
		{
			if (flag2)
			{
				fo(x,1,n)
				{
					i=lst[x];
					while (i)
					{
						y=e[i][1];
						if (y<x) d[x]=e[i][2], h[x]=e[i][3];
						i=e[i][0];
					}
					f[x]=f[x-1]+d[x];
				}
				fo(i,1,q)
				{
					scanf("%d%d",&x,&y), x=(x+k0*lans-1) %n+1, y=(y+k0*lans) %(s+1);
					while (x>1 && h[x]>y) x--;
					printf("%d\n",f[x]), lans=f[x];
				}
			}
			else
			{
				build(1);
				fo(j,1,W) fo(i,1,n)
				{
					fa[i][j]=fa[fa[i][j-1]][j-1];
					g[i][j]=max(g[i][j-1],g[fa[i][j-1]][j-1]);
				}
				fo(i,1,q)
				{
					scanf("%d%d",&x,&y), x=(x+k0*lans-1) %n+1, y=(y+k0*lans) %(s+1);
					for (j=W; j>=0; j--)
						while (fa[x][j] && g[x][j]>y) x=fa[x][j];
					printf("%d\n",f[x]), lans=f[x];
				}
			}
		}
		else
		{
			spfa(); //
			fo(i,1,q) scanf("%d%d",&c[i].x,&c[i].h), c[i].i=i;
			sort(c+1,c+q+1,cmp), t=0;
			fo(x,1,n)
			{
				i=lst[x], h[x]=x;
				while (i)
				{
					y=e[i][1];
					if (y<x) c2[++t].x=y, c2[t].y=x, c2[t].h=e[i][3];
					i=e[i][0];
				}
			}
			sort(c2+1,c2+m+1,cmp2);
			j=1; 
			fo(i,1,q)
			{
				while (j<=m && c2[j].h>c[i].h) merge(c2[j].x,c2[j].y), j++;
				d[c[i].i]=f[find(c[i].x)];
			}
			fo(i,1,q) printf("%d\n",d[i]);
		}
	}
}

评测结果