1438: Benjam1n_蓝桥杯2013年第四届真题-大臣的旅费（C++代码）

解题思路:
链式前向星+深搜
参考代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010 , M = 200010;
int h[N] ,e[M], ne[M] ,w[M],idx;
int f[N];

void add(int a,int b,int c){
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

void dfs(int u,int fa,int dis){
    f[u]=dis;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j = e[i];
        if(j!=fa)
            dfs(j,u,f[u]+w[i]);
    }
}

signed main(){
    int n;
    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);
    }
    dfs(1,-1,0);
    int u = 1;
    for(int i=2;i<=n;i++)
        if(f[i]>f[u])
            u=i;
    dfs(u,-1,0);
    int _max = f[1];
    for(int i=2;i<=n;i++)
        if(f[i]>_max)
            _max=f[i];
    cout<<(_max * 10 + ((long)(_max + 1) * _max ) / 2);
    return 0;
}