深搜写法

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
struct Edge
{
    int des, wei;   //目的地 权重
};
int n, ans = 2e9;
vector<Edge> vec[1005];
void dfs(int now, int pre, int sum)
{
    ans = min(ans, sum);
    for (auto i : vec[now])
    {
        if (i.des == pre)
            continue;
        dfs(i.des, now, sum + i.wei);
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        vec[u].push_back((Edge){v, w});
        vec[v].push_back((Edge){u, w});
    }
    for (int i = 1; i <= n; i++)
        dfs(i, 0, 0);
    cout << ans << endl;
}

本题做法很多，考虑到数据范围就 $1000$，所以最简单的做法就是枚举每个点作为起点时到其他所有点的距离，即选择当前点作为根时的每个节点的深度，采用 dfs 或 bfs 皆可，时间复杂度为 $O(n^2)$，这里给出 bfs 的代码。

int main()
{
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
        e[v].push_back((Edge){u, w});
    }
    int ans = 1000005;
    for (int i = 1; i <= n; i++)
    {
        while (!q.empty())
            q.pop();
        for (int j = 1; j <= n; j++)
            vis[j] = false;
        q.push(i);
        vis[i] = true;
        dis[i] = 0;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int j = 0; j < e[u].size(); j++)
            {
                int v = e[u][j].v;
                int w = e[u][j].w; 
                
                if (vis[v])
                    continue;
                dis[v] = dis[u] + w;
                vis[v] = true;
                q.push(v);
                ans = min(ans, dis[v]);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}