本文共 1852 字，大约阅读时间需要 6 分钟。

   
   
   
   
#include 
   
    
using namespace std;
const int N = 50010;
struct Edge {
    int v, w;
};
int f[N][20], d[N], dist[N];
vector
    
      son[N];
int T, n, m, tot, t;
queue
     
       q;
void bfs() {
    memset(d, 0, sizeof(d));
    q.push(1);
    d[1] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < son[x].size(); i++) {
            int v = son[x][i].v, w = son[x][i].w;
            if (d[v]) continue;
            d[v] = d[x] + 1;
            dist[v] = dist[x] + w;
            f[v][0] = x;
            for (int j = 1; j <= t; j++) {
                f[v][j] = f[f[v][j-1]][j-1];
            }
            q.push(v);
        }
    }
}
int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    for (int i = t; i >= 0; i--) {
        if (d[f[y][i]] >= d[x]) y = f[y][i];
        if (x == y) return x;
        for (int i = t; i >= 0; i--) {
            if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
        }
        return f[x][0];
    }
}
int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        t = (int)(log(n) / log(2)) + 1;
        tot = 0;
        for (int i = 1; i <= n; i++) son[i].clear();
        for (int i = 1; i <= n; i++) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            son[x].push_back({y, z});
            son[y].push_back({x, z});
        }
        bfs();
        cin >> m;
        for (int i = 1; i <= m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", dist[x] + dist[y] - 2 * dist[lca(x, y)]);
        }
    }
}
     
    
   

这段代码实现了一个基于广度优先搜索（BFS）的最低公共祖先（LCA）算法，用于处理无向图中的最短路径问题。代码的主要功能包括：

代码的实现思路包括：

• 广度优先搜索（BFS）：用于计算节点的深度和到根节点的距离。
• 跳跃指针技术：预处理每个节点的跳跃表，使得LCA查询效率更高。
• 动态规划：用于处理跳跃表中的父指针更新。

代码结构清晰，注释完整，易于理解和维护。

转载地址：http://pawn.baihongyu.com/