BFS算法代码实现

本题可使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来求解村庄间的最短路径，以下是使用BFS算法的C++代码实现：

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 40005;
vector<pair<int, int>> graph[MAXN]; // 邻接表存储图，pair.first为邻居节点，pair.second为边的权重
int dist[MAXN]; // 记录从起点到各点的距离

void bfs(int start, int end) {
    queue<int> q;
    memset(dist, -1, sizeof(dist));
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[v] == -1) {
                dist[v] = dist[u] + w;
                if (v == end) {
                    return;
                }
                q.push(v);
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n - 1; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            bfs(a, b);
            cout << dist[b] << endl;
        }
        for (int i = 1; i <= n; ++i) {
            graph[i].clear();
        }
        cout << endl;
    }
    return 0;
}

代码解释：

1.首先定义了图的存储结构 graph 为邻接表，dist 数组用于记录从起点到各点的距离。
2.bfs 函数实现了广度优先搜索算法，从起点 start 开始搜索，直到找到终点 end，并记录路径距离。
3.在 main 函数中，先读取测试数据组数 T，对于每组测试数据，读取村庄数量 n 和询问数量 m ，然后读取 n - 1 条边的信息构建图。接着对于每个询问，调用 bfs 函数求解并输出结果。最后在每组测试数据结束后，清空图的邻接表并输出一个空行。

最终代码：

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 40005;
vector<pair<int, int>> graph[MAXN];
int dist[MAXN]; 

void bfs(int start, int end) {
    queue<int> q;
    memset(dist, -1, sizeof(dist));
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[v] == -1) {
                dist[v] = dist[u] + w;
                if (v == end) {
                    return;
                }
                q.push(v);
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n - 1; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            bfs(a, b);
            cout << dist[b] << endl;
        }
        for (int i = 1; i <= n; ++i) {
            graph[i].clear();
        }
        cout << endl;
    }
    return 0;
}