link
如果把所有互相之间的边没有积水的点看成一个个的块，显然块内部可以开车直接到达，也就是说块内部所有点的答案是一样的；
我们可以先用dij把每一个点到1号点的最短路预处理出来，建一棵kruskal重构树，然后在dfs时把这一个子树内的最小答案挂在根节点上；
最后我们倍增找到出发节点所在块的根节点（最浅的那一个），输出其答案即可；
#include<bits/stdc++.h>
#define m(a) memset(a, 0, sizeof(a))
using namespace std;
const int N = (2e5 + 5) * 2;
const int M = 4e5 + 5;
int T, n, m, q, k, s, dis[N], vis[N], fa[N], f[N][22], dq[N];
vector<pair<int, int> > mp[N];
vector<int> tr[N];
struct edge{int u, v, l, a;
}e[M];
struct node{int id, w;friend bool operator <(node a, node b) {return a.w > b.w;}
};
bool cmp(edge x, edge y){return x.a > y.a;
}
int find(int x){if(fa[x] == x) return x;return fa[x] = find(fa[x]);
}
void dij(){priority_queue<node> q;for(int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f;dis[1] = 0;q.push({1, 0});while(!q.empty()){int u = q.top().id;q.pop();if(vis[u]) continue;vis[u] = 1;for(auto tmp : mp[u]){int v = tmp.first;int w = tmp.second;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push({v, dis[v]});}}}
}
void kruskal(){sort(e + 1, e + m + 1, cmp);for(int i = 1; i <= n; i++) fa[i] = i, dq[i] = 0;for(int i = 1; i <= m; i++){int f1 = find(e[i].u);int f2 = find(e[i].v);if(f1 == f2) continue;fa[f1] = fa[f2] = fa[++n] = n;dq[n] = e[i].a; dis[n] = 0x3f3f3f3f;tr[n].push_back(f1); tr[n].push_back(f2);}
}
void dfs(int u, int father){f[u][0] = father;for(int j = 1; j <= 20; j++) f[u][j] = f[f[u][j - 1]][j - 1];for(auto v : tr[u]){dfs(v, u);dis[u] = min(dis[u], dis[v]);}
}
int main(){cin >> T;while(T--){int lastans = 0;m(e); m(tr); m(vis); m(dis); m(fa); m(f); m(dq);cin >> n >> m;int cnt = n;for(int i = 1; i <= n * 2; i++) mp[i].clear(), tr[i].clear();for(int i = 1; i <= m; i++){cin >> e[i].u >> e[i].v >> e[i].l >> e[i].a;mp[e[i].u].push_back({e[i].v, e[i].l});mp[e[i].v].push_back({e[i].u, e[i].l});}cin >> q >> k >> s;dij();kruskal();dfs(n, n);for(int i = 1; i <= q; i++){int v0, p0;cin >> v0 >> p0;int c = (v0 + k * lastans - 1) % cnt + 1;int p = (p0 + k * lastans) % (s + 1);for(int j = 20; j >= 0; j--){if(dq[f[c][j]] > p){c = f[c][j];} } lastans = dis[c];cout << lastans << endl;}}
}