题意分析

题目要求求给的所有村庄中距离最远的两个村庄

解题思路

题目说明任意两个村庄之间只有一条不重复经过其他村庄的路径，说明这是一个树形结构，因此，求距离最远的两个村庄就是求一个树的直径。可以重复两次bfs找到树的直径，第一次找到任意一个节点的最远点，第二次找到最远点的最远点（即直径）。

标程

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

pair<int, long long> bfs(int start, unordered_map<int, vector<pair<int, int>>>& graph) {
    unordered_map<int, long long> dist;
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    long long maxDist = 0;
    int farNode = start;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (dist[u] > maxDist) {
            maxDist = dist[u];
            farNode = u;
        }
        if (graph.find(u) != graph.end()) {
            for (const auto& edge : graph[u]) {
                int v = edge.first;
                long long w = edge.second;
                if (dist.find(v) == dist.end()) {
                    dist[v] = dist[u] + w;
                    q.push(v);
                }
            }
        }
    }
    return {farNode, maxDist};
}

int main() {
    unordered_map<int, vector<pair<int, int>>> graph;
    int a, b, c;

    while (cin >> a >> b >> c) {
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    if (graph.empty()) {
        cout << 0 << endl;
        return 0;
    }

    int start_node = graph.begin()->first;
    auto first_bfs_result = bfs(start_node, graph);
    auto second_bfs_result = bfs(first_bfs_result.first, graph);

    cout << second_bfs_result.second << endl;

    return 0;
}