牛客练习赛24 D-插排树 【单源最长路经】

链接：https://www.nowcoder.com/acm/contest/157/D
来源：牛客网
 

题目描述

一年一度的山东省oi夏令营又开始了，每到这个季节，山东的oier们都会欢聚这里，一起学（tuí）习（feì）。当然，为了能更加愉快地学（tuí）习（feì），就少不了要自带电脑，用电便开始成了一种问题，于是便有一种神奇的数据结构诞生了！这就是山东省oi专用数据结构——插排树（如图）

小K为了能更好的学（tuí）习（feì），所以他想尽量的往后做，所以现在请你帮帮他，他最远可以离讲台多远。

已知插排树的根节点在讲台上，有且仅有一个根节点（根节点入度为0），最远距离即所有插排的长度，小K电脑线的长度忽略不计

 

本题良心大样例下载地址： https://kench.co/tree.zip

输入描述:

第一行一个整数n表示有n个节点
然后n-1行，每行三个整数a,b,c，表示插排a是接在插排b上的，插排a的长度为c

输出描述:

一个整数n表示最远距离

示例1

输入

复制

9
2 1 2
3 1 2
4 1 1
5 2 3
6 2 1
7 3 1
8 3 4
9 7 5

输出

复制

8

说明

1=>3=>7=>9

备注:

对于30%的数据 n<233
对于70%的数据 n<2333

对于100%的数据 n<50000

c小于20

a,b小于等于n

---

思路:注意一下本题没说讲台 也就是根节点是哪个点 没了

---

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define maxn 500005
#define mod 1e9+7
#define inf 1e18
typedef long long ll;
ll n,head[maxn],num,ans[maxn],flag[maxn];
set<ll>goushi;
struct Why
{
    ll next,now,dis;
}plat[maxn];
struct Whhy
{
    ll now,dis;
    Whhy(ll a,ll b)
    {
        now = a;
        dis = b;
    }
    bool operator <(const Whhy a) const
    {
        return dis < a.dis;
    }
};
void build(ll a,ll b,ll c)
{
    plat[++num].next = head[a];
    plat[num].now = b;
    plat[num].dis = c;
    head[a] = num;
    return ;
}
void bfs(ll x)
{
    priority_queue<Whhy>A;
    A.push( Whhy(x,0) );
    while(!A.empty())
    {
        Whhy temp = A.top();
        A.pop();
        if( flag[ temp.now ] == 0 )
        {
            flag[ temp.now ] = 1;
            if(temp.dis > ans[ temp.now ])
                ans[ temp.now ] = temp.dis;
            for(ll i = head[ temp.now ]; i != 0; i = plat[ i ].next)
            {
                A.push( Whhy( plat[i].now, plat[i].dis+temp.dis ) );
            }
        }
    }
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(ll i = 1; i <= n; i++)
        goushi.insert(i);
    for(ll i = 1; i < n; i++)
    {
        ll a,b,c;
        cin >> a >> b >> c;
        build(b,a,c);
        goushi.erase(a);
    }
    bfs(*goushi.begin());
    //for(ll i = 1; i <= n; i++)
    //    cout << ans[i] << " ";
    sort(ans+1,ans+1+n);
    cout << ans[n] << endl;
    return 0;
}