代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}

void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}

const int N = 400005,M = 400005;

struct edge{
int head[N<<1],nxt[M<<1],to[M<<1],val[M<<1],cnt;

edge() {memset(head,-1,sizeof(head));}

void add(int u,int v,int w) {
    nxt[cnt] = head[u];
    to[cnt] = v;
    val[cnt] = w;
    head[u] = cnt++;
}
}g,G;

struct ED{
    int x,y,a;
}E[M];

struct node{
    int x,d;
    node(int x,int d) : x(x),d(d){}
    friend bool operator < (node a,node b) {
        return a.d > b.d;
    }
};

bool cmp(ED a,ED b) {
    return a.a > b.a;
}

int n,m,dis[N<<1],mn[N<<1],fa[N<<1][21],s[N<<1],v[N<<1];
bool vis[N<<1];

void dij() {
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    priority_queue<node> q;
    q.emplace(node(1,0));
    dis[1] = 0;
    while(q.size()) {
        node t = q.top();
        q.pop();
        if(vis[t.x]) continue;
        vis[t.x] = true;
        for(int i = g.head[t.x];~i;i = g.nxt[i]) {
            int y = g.to[i];
            if(dis[y] > dis[t.x] + g.val[i]) {
                dis[y] = dis[t.x] + g.val[i];
                q.emplace(node(y,dis[y]));
            }
        }
    }
}

int find(int x) {
    if(s[x] ^ x) s[x] = find(s[x]);
    return s[x];
}

void dfs(int x,int f) {
    fa[x][0] = f;mn[x] = dis[x];
    for(int i = 1;i<=20;i++) fa[x][i] = fa[fa[x][i-1]][i-1];
    for(int i = G.head[x];~i;i = G.nxt[i]) {
        int y = G.to[i];
        dfs(y,x);
        mn[x] = min(mn[x],mn[y]);
        
    }
}

void kruskalTree(){
    sort(E + 1,E + m + 1,cmp);
    int now = n;
    for(int i = 1;i<=n * 3;i++) s[i] = i;
    for(int i = 1;i<=m;i++) {
        int fx = find(E[i].x),fy = find(E[i].y);
        if(fx ^ fy) {
            s[fx] = s[fy] = ++now;
            v[now] = E[i].a;
            s[now] = now;
            G.add(now,fx,1);G.add(now,fy,1);
        }
    }
    dfs(now,0);
}

void solve() {
    memset(g.head,-1,sizeof(g.head));
    g.cnt = 0;
    memset(G.head,-1,sizeof(G.head));
    G.cnt = 0;
    n = rd(),m = rd();
    for(int i = 1;i<=m;i++) {
        int x = rd(),y = rd(),l = rd(),a = rd();
        E[i].x = x;E[i].y = y;E[i].a = a;
        g.add(x,y,l);g.add(y,x,l);
    }
    dij();
    kruskalTree();
    int Q = rd(),K = rd(),S = rd();
    int last = 0;
    while(Q--) {
        int V = rd(),p = rd();
        V = (V + K * last - 1) % n + 1;
        p = (p + K * last) % (S + 1);
        for(int i = 20;i>=0;i--)
            if(fa[V][i] && v[fa[V][i]] > p) 
                V = fa[V][i];
        wt(last = mn[V]);
        putchar('\n');
    }   
}

signed main() {
    int T = rd();
    while(T--) solve();
	return 0;
}

评测结果