算法

bfs

时间复杂度

O(n)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=200020;//无向图  指针加倍
int n,m;
int h[N],e[M],ne[M],idx,w[M],d[N];
int st[N];
void bfs(int u)
{
    queue<int> q;
    memset(st,0,sizeof st);//一定要初始化
    q.push(u);
    st[u]++;d[u]=0;//标记  d数组记录该点到bfs的第一个点的距离
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]++;
            d[j]=d[t]+w[i];//更新搜到的点到初始点的距离
            q.push(j);
        }

    }
    }

}
void add(int a,int b,int c)
{
    e[idx]=b;ne[idx]=h[a];w[idx]=c;h[a]=idx++;//idx++一定要在最后！！
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);//初始化头指针
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);add(b,a,c);
    }
    bfs(1);//搜索离1号点的所有点的距离
    int u=1;
    for(int i=1;i<=n;i++ )
        if(d[i]>d[u]) u=i;

    bfs(u);//找到离一号点最远的点u 再找离U最远的点  之后最长的距离即为树的直径
    int maxx=d[1];int t;
    for(int i=2;i<=n;i++ )
        if(d[i]>maxx) 
        {
             t=i;maxx=d[i];
        }
    cout<<maxx * 10 + ((long)(maxx + 1) * maxx ) / 2<<endl;//根据题意推路费公式
    return 0;
}