NC19814 最短路(LCA)

题目链接

题意：

题解：

AC代码

/*
    Author : zzugzx
    Lang : C++
    Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9+7;
//const int mod = 998244353;
const double eps = 1e-10;
const double pi = acos(-1.0);
const int maxn = 1e6+10;
const ll inf = 0x3f3f3f3f;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int n, m, depth[maxn], f[maxn][50];
int from[maxn], to[maxn << 1], nxt[maxn << 1], cnt = 1, Log[maxn], From[maxn];
bool vis[maxn], used[maxn];
//链式前向星加边
void addEdge (int u, int v) {
    From[++cnt] = u, to[cnt] = v, nxt[cnt] = from[u], from[u] = cnt;
}
//计算深度&计算祖先
void dfs (int u, int fa) {
    depth[u] = depth[fa] + 1;
    vis[u] = 1;
    for (register int i = 1; i <= Log[n]; ++i) {
        if ((1 << i) > depth[u]) break;
        f[u][i] =  f[f[u][i - 1]][i - 1];
    }
    for (register int i = from[u]; i; i = nxt[i]) {
        ll v = to[i];
        if (vis[v]) continue;
        used[i] = used[i ^ 1] = 1;
        f[v][0] = u;
        dfs (v, u);
    }
}
//计算LCA
inline int LCA (int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    //我们默认x为更深的那个点
    for(register int i = Log[n] ; i >= 0 ; --i)
        if(depth[x] - (1 << i) >= depth[y]) x = f[x][i];
    //将x跳到和y同一深度上
    if (x == y) return x;
    for (register int i = Log[n]; i >= 0; --i)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    //一起向上跳
    return f[x][0];
    //不难看出，此时两个点均在其LCA的下方，往上跳一次即可
}
void init(){
    Log[0] = -1;
    for (register int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        addEdge (u, v); addEdge(v, u);
        Log[i] = Log[i >> 1] + 1;
    }
    Log[n] = Log[n >> 1] + 1;
    dfs(1, 0);
}
int dist(int p , int q){return depth[p] + depth[q] - 2 * depth[LCA(p , q)];}
int ans[maxn],a[maxn],b[maxn],dis[maxn], Q, q[maxn], h, t;
void bfs(int s){
    for (int i = 1; i <= n; i++)dis[i] = inf;
    dis[s] = 0;
    h = t = 0;
    q[++h] = s;
    while (t < h) {
        int u = q[++t];
        for (int i = from[u]; i; i = nxt[i]){
            int v = to[i];
            if (dis[v] > dis[u] + 1)
                dis[v] = dis[u] + 1, q[++h] = v;
        }
    }
    for (int i = 1; i <= Q; i++)
        ans[i] = min(ans[i], dis[a[i]] + dis[b[i]]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    cin >> n >> m;
    init();
    cin >> Q;
    for (int i = 1; i <= Q; i++){
        cin >> a[i] >> b[i];
        ans[i] = dist(a[i], b[i]);
    }
    int num = 0;
    for (int i = 2; i <= cnt; i++)
        if(!used[i]) {
            used[i] = used[i ^ 1] = 1;
            bfs(From[i]);
            num++;
            if(num > 101) break;
        }
    for (int i = 1; i <= Q; i++)
        cout << ans[i] << endl;
    return 0;
}