(mathcal{Description})
Link.
给定一个 (n) 个点 (m) 条边的无向连通图，边形如 ((u,v,l,a))。每次询问给出 (u,p)，回答所有从 (u) 出发，只经过 (a) 值 (>p) 的边能够到达的点中，到 (1) 号点的最小距离（以 (l) 之和为路径距离）。强制在线，多测。
(nle2 imes 10^5)，(m,qle4 imes 10^5)。
(mathcal{Solution})
Kruskal 生成树的板子，还是当做算法总结写一下吧。（
Kruskal 生成树就是在用 Kruskal 求最小（最大）生成树时，以加入边的边权作为虚点点权，并从虚点连向左右两个联通块的根，使虚点成为新连通块的根，最终构成的一棵大根（小根）树堆。
对于本题，构最大生成树，答案即为子树内点到 (1) 最短路的最小值。复杂度 (mathcal O(Tleft((n+q)log n+mlog m ight)))。
(mathcal{Code})
/* Clearink */
#include <queue>
#include <cstdio>
#include <algorithm>
typedef std::pair<int, int> pii;
typedef std::pair<int, std::pair<int, int> > EdgeT;
inline int rint () {
int x = 0; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () );
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x;
}
inline void wint ( int x ) {
if ( x < 0 ) putchar ( '-' ), x = -x;
if ( 9 < x ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
inline void chkmin ( int& a, const int b ) { a > b ? a = b : 0; }
const int MAXN = 4e5, MAXLG = 18;
int n, m, node, len[MAXN + 5], val[MAXN + 5], dist[MAXN + 5];
int fa[MAXN + 5][MAXLG + 5], mndist[MAXN + 5];
EdgeT edge[MAXN + 5];
struct Graph {
int ecnt, head[MAXN + 5], to[MAXN * 2 + 5], nxt[MAXN * 2 + 5];
Graph (): ecnt ( 1 ) {}
inline void link ( const int s, const int t ) {
to[++ ecnt] = t, nxt[ecnt] = head[s];
head[s] = ecnt;
}
} G, T;
struct DSU {
int fa[MAXN + 5];
inline int find ( const int x ) { return x ^ fa[x] ? fa[x] = find ( fa[x] ) : x; }
} dsu;
inline void buildKT () {
node = n;
std::sort ( edge + 1, edge + m + 1, []( const auto& a, const auto& b ) {
return a.first > b.first;
} );
for ( int i = 1; i <= n; ++ i ) dsu.fa[i] = i;
for ( int i = 1, u, v; i <= m; ++ i ) {
if ( ( u = dsu.find ( edge[i].second.first ) )
!= ( v = dsu.find ( edge[i].second.second ) ) ) {
val[++ node] = edge[i].first;
dsu.fa[u] = dsu.fa[v] = dsu.fa[node] = node;
T.link ( node, u ), T.link ( node, v );
}
}
}
inline void Dijkstra () {
static bool vis[MAXN + 5];
static std::priority_queue<pii, std::vector<pii>, std::greater<pii> > heap;
for ( int i = 1; i <= n; ++ i ) dist[i] = -1, vis[i] = false;
heap.push ( { dist[1] = 0, 1 } );
while ( !heap.empty () ) {
pii p ( heap.top () ); heap.pop ();
if ( vis[p.second] ) continue;
vis[p.second] = true;
for ( int i = G.head[p.second], v; i; i = G.nxt[i] ) {
if ( int t = p.first + len[i >> 1]; !~dist[v = G.to[i]] || dist[v] > t ) {
heap.push ( { dist[v] = t, v } );
}
}
}
}
inline void prepKT ( const int u ) {
for ( int i = 1; i <= 18; ++ i ) fa[u][i] = fa[fa[u][i - 1]][i - 1];
mndist[u] = u <= n ? dist[u] : 0x7fffffff;
for ( int i = T.head[u], v; i; i = T.nxt[i] ) {
fa[v = T.to[i]][0] = u, prepKT ( v );
chkmin ( mndist[u], mndist[v] );
}
}
inline int climb ( int u, const int p ) {
for ( int i = 18; ~i; -- i ) if ( fa[u][i] && val[fa[u][i]] > p ) u = fa[u][i];
return u;
}
inline void clear () {
G.ecnt = T.ecnt = 1;
for ( int i = 1; i <= node; ++ i ) G.head[i] = T.head[i] = 0;
}
int main () {
for ( int T = rint (); T --; ) {
clear ();
n = rint (), m = rint ();
for ( int i = 1, u, v, a; i <= m; ++ i ) {
u = rint (), v = rint (), len[i] = rint (), a = rint ();
G.link ( u, v ), G.link ( v, u ), edge[i] = { a, { u, v } };
}
buildKT (), Dijkstra (), prepKT ( node );
for ( int q = rint (), k = rint (), s = rint (), ans = 0, u, p; q --; ) {
u = ( rint () + k * ans - 1 ) % n + 1;
p = ( rint () + k * ans ) % ( s + 1 );
wint ( ans = mndist[climb ( u, p )] ), putchar ( '
' );
}
}
return 0;
}
(mathcal{Details})
多测不清空，爆零两行泪 qwq。