代码

#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=15;
int t0, n, m, q, k0, s, i, j, x, y, t1, t2, t, lans, ans;
int lst[N], e[M*2][4];
int data[N*10], f[N], d[N], h[N];
int fa[N][W], g[N][W];
bool bz[N];
bool flag, flag2;

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 spfa()
{
	int i=0, j=1; data[1]=1;
	memset(f,80,sizeof(f)), f[1]=0;
	memset(bz,0,sizeof(bz));
	while (i<j)
	{
		int x=data[++i], k=lst[x]; bz[x]=0;
		while (k)
		{
			int y=e[k][1];
			if (f[x]+e[k][2]<f[y])
			{
				f[y]=f[x]+e[k][2];
				if (!bz[y]) bz[y]=1, data[++j]=y;
			}
			k=e[k][0];
		}
	}
}
void bfs(int x,int h0)
{
	int i=0, j=1; data[1]=x;
	memset(bz,0,sizeof(bz)), bz[x]=1;
	while (i<j)
	{
		x=data[++i]; int k=lst[x];
		while (k)
		{
			int y=e[k][1];
			if (!bz[y]) 
			{
				if (e[k][3]<=h0) ans=min(ans,f[y]+e[k][2]); else 
				if (y==1) { ans=0; return;} else bz[data[++j]=y]=1;
			}
			k=e[k][0];
		}
	}
}
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);
		}
	}
}

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",&x,&y), x=(x+k0*lans-1) %n+1, y=(y+k0*lans) %(s+1);
				ans=f[x], bfs(x,y), printf("%d\n",ans), lans=ans;
			}
		}
	}
}

评测结果