题目描述

算法1

仅记录，看注释。

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

const int N=1e4+10,M=2*N,INF=0x3f3f3f3f;

int n;
int h[N],ne[M],w[M],e[M],idx;
int d1[N],d2[N],up[N],p1[N],p2[N];//分别维护最大值和次大值和对应的路径
bool is_leaf[N];        //需要判断是否是叶子节点，如果直接更改为0的话，边权为负可能无法通过

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

int dfs_d(int u,int father)     //向下走的路径递归函数
{
    if(h[u]==-1) return 0;

    d1[u]=d2[u]=-INF;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==father) continue;
        int d=dfs_d(j,u) +w[i];
        if(d>=d1[u]) 
        {
            d2[u]=d1[u],d1[u]=d;
            p2[u]=p1[u],p1[u]=j;
        }
        else if(d>d2[u]) d2[u]=d,p2[u]=j;
    }
    if(d1[u] == -INF)//d1[u]是叶子结点,没有更新
    {
        d1[u] = d2[u] = 0;
        is_leaf[u] = true;
    }

    return d1[u];
}

void dfs_u(int u,int father)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==father) continue;

        if(p1[u]==j) up[j]=max(up[u],d2[u])+w[i];
        else up[j]=max(up[u],d1[u])+w[i];
        dfs_u(j,u);
    }
}

int main()
{
    cin>>n;

    memset(h,-1,sizeof h);

    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;

        add(a,b,c);
        add(b,a,c);
    }

    dfs_d(1,-1);    //选择第一个点为根节点
    dfs_u(1,-1);

    int res=d1[1];
    for (int i = 2; i <= n; i ++ )      //这里2号点开始枚举，因为up数组的更新是从根节点开始（不包括），所以根节点(1)对应的up值为0。
        if (is_leaf[i]) res = min(res, up[i]);
        else res = min(res, max(d1[i], up[i]));

    cout<<res<<endl;

    return 0;
}