最简单作法,一看就懂
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010;
int h[N], e[N], ne[N], w[N], idx;
int d1[N]; //保存每个节点向下走的最长子路径
int n, ans;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dfs_down(int u, int fa)
{
int d2 = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
int d = dfs_down(j, u) + w[i];
if (d >= d1[u])
{
d2 = d1[u];
d1[u] = d;
}
else if (d >= d2) d2 = d;
}
ans = max(d1[u] + d2, ans); //求出最长的路径
return d1[u];
}
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 1; i < n; i ++)
{
int a, b, c;
scanf("%d%d%d", &a,&b,&c);
add(a, b, c);
add(b, a, c);
}
dfs_down(1, -1);
int res = d1[1];
for (int i = 1; i <= n; i ++)
res = min(res, max(d1[i],ans - d1[i])); //向下走的最长路径和另一段进行比较,选择最大的
cout << res;
return 0;
}
同样类型的这样写不一定正确