题目意思

给出n个点，最多只会有n+100条边，问给出q次询问，每次询问的两个点最短距离是什么，规模都是1e5

解题思路

第一想法：floyd算法，再看下问题规模，1e5，因为floyd基于邻接矩阵存储而且要On^3空间时间都不满足。

换个方向，题目给出的数据范围要仔细琢磨，最多的只有n+100条边说明就说在一颗树上添加了一点点边而已，那么我们就知道，如果不看这100条边，把他当成一颗树来看就可以用倍增的LCA去求树上最短距离，这里不展开可以去百度或者看看代码，那么还有就是剩下的100条边如何处理，它们在什么情况下会更新答案？我们在处理边信息的时候如果一条边的左右点都有同一个父亲说明这条边不是树上n-1中的边把他放到另外的set存储起来，把全部的点保存之后，再跑dijkstra，看看多余的边有没有能把路径变得更短的就行了。

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }


const int N = 1e5 + 200; //节点数
int n, m, head[N], to[N << 1], nex[N << 1], tot;
vector<int> g[N];
int d[N][210], p[210], pt;
void init() {
    memset(head, -1, sizeof(head));
    tot = 0;
}
void add(int x, int y) {
    to[tot] = y;
    nex[tot] = head[x];
    head[x] = tot++;
}
int fa[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}


// LCA直接求树上最短距离，倍增
int h[N], f[N][20], TT, len[N];
void dfs(int x, int y) {
    h[x] = h[y] + 1;
    f[x][0] = y;
    for (int i = 1; i <= TT; ++i)    f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = 0; i < g[x].size(); ++i) {
        int v = g[x][i];
        if (v != y) {
            len[v] = len[x] + 1;
            dfs(v, x);
        }
    }
}
int LCA(int x, int y) {
    if (h[x] > h[y])    swap(x, y);
    for (int i = TT; ~i; --i)
        if (h[f[y][i]] >= h[x])    y = f[y][i];
    if (x == y)    return x;
    for (int i = TT; ~i; --i)
        if (f[y][i] != f[x][i])
            y = f[y][i], x = f[x][i];
    return f[x][0];
}


// 对于不是树中的n-1条边的其余边直接跑dijkstra求道最短路，尝试更新答案即可
set<int> sp;
bool vis[N];
void dijkstra(int s, int id) {
    memset(vis, 0, sizeof(vis));
    queue<int> que;
    que.push(s);
    d[s][id] = 0;
    while (que.size()) {
        int u = que.front();    que.pop();
        if (vis[u])    continue;
        vis[u] = 1;
        for (int i = head[u]; ~i; i = nex[i]) {
            int v = to[i];
            if (!vis[v] and d[v][id] > d[u][id] + 1)
                d[v][id] = d[u][id] + 1, que.push(v);
        }
    }
}

int main() {
    init();
    int n = read(), m = read();
    int cnt = 0;
    for (int i = 1; i <= n; ++i)    fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int x = read(), y = read();
        add(x, y), add(y, x);
        if (cnt == n - 1) {
            if (!sp.count(x))    sp.insert(x), p[++pt] = x;
            continue;
        }
        int fu = find(x), fv = find(y);
        if (fu == fv) {
            if (!sp.count(x))    sp.insert(x), p[++pt] = x;
            continue;
        }
        g[x].push_back(y), g[y].push_back(x);
        ++cnt, fa[fu] = fa[fv];
    }
    TT = int(log(n) / log(2)) + 1; //最高的树高
    dfs(1, 0);
    memset(d, 127, sizeof(d));
    for (int i = 1; i <= pt; ++i)
        dijkstra(p[i], i);
    int q = read();
    while (q--) {
        int u = read(), v = read();
        int ans = len[u] + len[v] - 2 * len[LCA(u, v)];
        for (int i = 1; i <= pt; ++i)    ans = min(ans, d[u][i] + d[v][i]);
        print(ans), putchar(10);
    }
    return 0;
}