代码

#include<cstdio> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
inline int read() { 
	int x = 0,f = 1; 
	char c = getchar(); 
	while(c < '0' ||c > '9'){if(c == '-') f = -1;c = getchar();}  
	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar(); 
	return x * f; 
} 
const int maxn = 600007; 
int n,m; 

struct node { 
	int u,v,l,a,next; 
} edge[maxn << 1]; 
int head[maxn],num = 0; 
int A[maxn],k,s; 
inline void add_edge(int u,int v,int l,int a) { edge[++ num].v = v;edge[num].next = head[u],head[u] = num; edge[num].l = l; edge[num].a = a; } 
int q[(maxn * 10)],dis[maxn]; bool vis[maxn]; 
int lastans = 0; 
int spfa(int x) { 
	int l = 0,r = 0;  
	memset(vis,0,sizeof vis); 
	memset(dis,0x3f,sizeof dis); 
	q[++ r] = x; vis[x] = 1; dis[x] = 0; 
	while(l <= r) { 
		int u = q[++ l]; 
		for(int i = head[u];i;i = edge[i].next) { 
			int v = edge[i].v; 
			if(dis[v] > dis[u] + edge[i].l) { 
				dis[v] = dis[u] + edge[i].l; 
				if(!vis[v]) {q[++ r] = v,vis[v] = 1;} 
			} 
		} 
		vis[u] = 0; 
	} 
} 
void work1(int X) { 
	spfa(1); 
	int Q = read();int k = read(),s =  read(); 
	for(int v,p;Q --;) { 
		v = (read() + k * lastans - 1) % n + 1; 
		p = (read() + k * lastans) % (s + 1); 
		if(p >= X) printf("%d\n",dis[v]),lastans = dis[v]; 
		else puts("0"),lastans = 0; 
	} 
} 
int dad[maxn][25],h[maxn][25],deep[maxn]; 
void dfs(int x,int fa) {  
	for(int i = 0;dad[x][i];++ i) { 
		dad[x][i + 1] = dad[dad[x][i]][i]; 
			h[x][i + 1] = std::min(h[x][i],h[dad[x][i]][i]);  
	} 
	for(int i = head[x];i;i = edge[i].next) { 
		int v = edge[i].v; 
		if(v == fa) continue; 
		dis[v] = dis[x] + edge[i].l; 
		h[v][0] = edge[i].a; 
		dad[v][0] = x; 
		dfs(v,x); 
	} 
} 
int Jump(int x,int p) { 
	 for(int i = 20;i >= 0;-- i) 
		if(h[x][i] > p) x = dad[x][i];
	return lastans = dis[x]; 
} 
void work2() { 
	dfs(1,0); 
	int Q = read();int k = read(),s = read(); 
	for(int v,p;Q --;) { 
		v = (read() + k * lastans - 1) % n + 1; 
		p = (read() + k * lastans) % (s + 1); 
		printf("%d\n",Jump(v,p)); 
	} 
} 
void init() { 
	lastans = 0; 
	n = read(),m = read(); int cnt = 0; 
	for(int u,v,l,a,i = 1;i <= m;++ i) { 
		u = read(),v = read(),l = read(),a = read();  
		add_edge(u,v,l,a); add_edge(v,u,l,a);
		A[i] = a; 
		if(A[i] != A[i - 1]) cnt ++; 
	} 	
	if(cnt == 1) work1(A[1]); 
	else if(m == n - 1) work2(); 
} 
int main() { 
	//freopen("return4.in","r",stdin); //freopen("return.out","w",stdout); 
	int t = read(); while(t --) { 
		memset(head,0,sizeof head); num = 0; lastans = 0;
		init(); 
	} 
	return 0; 
} 

评测结果