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

   
   
   
   #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/