- #include < iostream > #include < cstdio > #include < cstring > #include < cstdlib > #include < algorithm > #define min(a, b)((a) < (b) ? (a) : (b))
- inline void read(int & x) {
- x = 0;
- char ch = getchar(),
- c = ch;
- while (ch < ‘0‘ || ch > ‘9‘) c = ch,
- ch = getchar();
- while (ch <= ‘9‘ && ch >= ‘0‘) x = x * 10 + ch - ‘0‘,
- ch = getchar();
- if (c == ‘ - ‘) x = -x;
- }
- inline void swap(int & a, int & b) {
- int tmp = a;
- a = b;
- b = tmp;
- }
- const int MAXN = 10000 + 10;
- const int MAXM = 50000 + 10;
- const int INF = 0x3f3f3f3f;
- int n,
- m,
- u[MAXM],
- v[MAXM],
- w[MAXM],
- cnt[MAXM],
- q,
- s,
- t,
- fa[MAXN],
- b[MAXM];
- bool cmp(int a, int b) {
- return w[a] > w[b];
- }
- struct Edge {
- int u,
- v,
- w,
- next;
- Edge(int _u, int _v, int _w, int _next) {
- u = _u,
- v = _v,
- w = _w,
- next = _next;
- }
- Edge() {}
- }
- edge[MAXN << 1];
- int head[MAXN],
- cntt;
- inline void insert(int a, int b, int c) {
- edge[++cntt] = Edge(a, b, c, head[a]);
- head[a] = cntt;
- }
- int deep[MAXN],
- p[20][MAXN],
- mi[20][MAXN];
- void dfs(int u) {
- b[u] = 1;
- for (register int pos = head[u]; pos; pos = edge[pos].next) {
- int v = edge[pos].v;
- if (b[v]) continue;
- deep[v] = deep[u] + 1;
- p[0][v] = u;
- mi[0][v] = edge[pos].w;
- dfs(v);
- }
- }
- void yuchuli() {
- int M = 0;
- while ((1 << M) <= n)++M; --M;
- for (register int i = 1; i <= M; ++i) for (register int j = 1; j <= n; ++j) p[i][j] = p[i - 1][p[i - 1][j]];
- for (register int i = 1; i <= M; ++i) for (register int j = 1; j <= n; ++j) mi[i][j] = min(mi[i - 1][p[i - 1][j]], mi[i - 1][j]);
- }
- int LCA(int va, int vb) {
- if (deep[va] < deep[vb]) swap(va, vb);
- int M = 0;
- while ((1 << M) <= n)++M; --M;
- for (register int i = M; i >= 0; --i) if (deep[vb] + (1 << i) <= deep[va]) va = p[i][va];
- if (va == vb) return va;
- M = 0;
- while ((1 << M) <= deep[va])++M; --M;
- for (register int i = M; i >= 0; --i) if (p[i][va] != p[i][vb]) {
- va = p[i][va];
- vb = p[i][vb];
- }
- return p[0][va];
- }
- int find(int x) {
- return x == fa[x] ? x: fa[x] = find(fa[x]);
- }
- int main() {
- read(n),
- read(m);
- for (register int i = 1; i <= m; ++i) read(u[i]),
- read(v[i]),
- read(w[i]),
- cnt[i] = i;
- for (register int i = 1; i <= n; ++i) fa[i] = i;
- std: :sort(cnt + 1, cnt + 1 + m, cmp);
- for (register int i = 1; i <= m; ++i) {
- int f1 = find(u[cnt[i]]),
- f2 = find(v[cnt[i]]);
- if (f1 != f2) {
- fa[f1] = f2;
- insert(u[cnt[i]], v[cnt[i]], w[cnt[i]]);
- insert(v[cnt[i]], u[cnt[i]], w[cnt[i]]);
- }
- }
- for (register int i = 1; i <= n; ++i) {
- if (!b[i]) {
- deep[i] = 1;
- dfs(i);
- }
- }
- yuchuli();
- read(q);
- int s,
- t;
- int M = 0;
- while ((1 << M) <= n)++M; --M;
- for (register int i = 1; i <= q; ++i) {
- read(s),
- read(t);
- int f1 = find(s),
- f2 = find(t);
- if (f1 != f2) {
- printf("-1\n");
- continue;
- }
- int lca = LCA(s, t);
- int mi1 = INF,
- mi2 = INF;
- for (register int j = M; j >= 0; --j) if (p[j][s] && deep[p[j][s]] >= deep[lca]) {
- mi1 = min(mi1, mi[j][s]);
- s = p[j][s];
- }
- for (register int j = M; j >= 0; --j) if (p[j][t] && deep[p[j][t]] >= deep[lca]) {
- mi2 = min(mi2, mi[j][t]);
- t = p[j][t];
- }
- printf("%d\n", min(mi1, mi2));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2314365.html