sideman 做好了回到 \text{Gliese}Gliese 星球的硬件准备，但是 \text{sideman}sideman 的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有 NN 个顶点和 MM 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。
\text{sideman}sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问 (A, B)(A,B)，\text{sideman}sideman 想知道从顶点 AA 航行到顶点 BB 所经过的最危险的边的危险程度值最小可能是多少。作为 \text{sideman}sideman 的同学，你们要帮助 \text{sideman}sideman 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。
输入输出格式
输入格式：
第一行包含两个正整数 NN 和 MM，表示点数和边数。
之后 MM 行，每行三个整数 AA，BB 和 LL，表示顶点 AA 和 BB 之间有一条边长为 LL 的边。顶点从 11 开始标号。
下面一行包含一个正整数 QQ，表示询问的数目。
之后 QQ 行，每行两个整数 AA 和 BB，表示询问 AA 和 BB 之间最危险的边危险程度的可能最小值。
输出格式：
对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出 \text{impossible}impossible。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int head[maxn], top[maxn], father[maxn]; int son[maxn], size[maxn], depth[maxn]; int fa[maxn], val[maxn], L[maxn], R[maxn], vis[maxn]; int n, m, q, u, v, tot, cnt, Index; struct Node { int u, v, w; bool operator < (const Node &x) const { return w < x.w; } }a[maxn]; struct Edge { int u, v, next; }edge[maxn]; int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void init() { memset(head, -1, sizeof(head)); tot = 1; } void add(int u, int v) { edge[++tot].u = u; edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot; } void dfs1(int u, int fa) { size[u] = 1; son[u] = 0; vis[u] = 1; father[u] = fa; depth[u] = depth[fa] + 1; int maxson = -1; for (int i = head[u]; i != -1; i = edge[i].next) { int to = edge[i].v; if (to == fa) { continue; } dfs1(to, u); size[u] += size[to]; if (size[to] > maxson) { maxson = size[to]; son[u] = to; } } } void dfs2(int u, int topf) { top[u] = topf; L[u] = R[u] = ++Index; if (son[u]) { dfs2(son[u], topf); } for (int i = head[u]; i != -1; i = edge[i].next) { int to = edge[i].v; if (top[to]) { continue; } dfs2(to, to); } R[u] = Index; } int LCA(int x, int y) { while (top[x] != top[y]) { if (depth[top[x]] < depth[top[y]]) { swap(x, y); } x = father[top[x]]; } if (depth[x] > depth[y]) { return y; } return x; } void kruskal() { for (int i = 1; i <= n; i++) { fa[i] = i; } sort(a + 1, a + m + 1); for (int i = 1; i <= m; i++) { int fu = find(a[i].u); int fv = find(a[i].v); if (fu != fv) { ++cnt; fa[cnt] = fa[fu] = fa[fv] = cnt; val[cnt] = a[i].w; add(cnt, fu); add(fu, cnt); add(cnt, fv); add(fv, cnt); } } for(int i=1;i<=cnt;++i) { if(!vis[i]){ int f=find(i); dfs1(f,0); dfs2(f,f); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); init(); cin >> n >> m; cnt = n; for (int i = 1; i <= m; i++) { cin >> a[i].u >> a[i].v >> a[i].w; } kruskal(); cin >> q; while (q--) { cin >> u >> v; if (find(u) != find(v)) { cout << "impossible" << endl; continue; } cout << val[LCA(u, v)] << endl; } return 0; }
