代码

#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*100], f[N], d[N], h[N];
int fa[N][W+1], g[N][W+1];
bool bz[N];
bool flag, flag2;
struct ques{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 spfa()
{
	int i=0, j=1, x, y, k; data[1]=1;
	memset(f,50,sizeof(f)), f[1]=0; 
	memset(bz,0,sizeof(bz));
	while (i<j)
	{
		x=data[++i], k=lst[x], bz[x]=0;
		while (k)
		{
			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;
					if (f[data[i+1]]>f[y]) data[j]=data[i+1], data[i+1]=y;
				}
			}
			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);
		}
	}
}

bool cmp(ques a,ques 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]);
		}
	}
}

评测结果