[NOI 2003] 逃学的小孩

[题目链接]

         https://www.lydsy.com/JudgeOnline/problem.php?id=1509

[算法]

       树的直径

[代码]

        

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010

struct edge
{
        int to,w,nxt;
} e[MAXN << 1];

int i,n,m,u,v,w,s,t,tot;
int head[MAXN];
long long dista[MAXN],distb[MAXN];
long long ans1,ans2;

inline void addedge(int u,int v,int w)
{
        tot++;
        e[tot] = (edge){v,w,head[u]};
        head[u] = tot;
}
inline int bfs(int s,long long *dist)
{
        int i,u,v,w,l,r,pos;
        static int q[MAXN];
        static bool visited[MAXN];
        memset(visited,false,sizeof(visited));
        q[l = r = 1] = s;
        visited[s] = true;
        dist[s] = 0;
        while (l <= r)
        {
                u = q[l];
                l++;
                for (i = head[u]; i; i = e[i].nxt)
                {
                        v = e[i].to;
                        w = e[i].w;
                        if (!visited[v])
                        {
                                dist[v] = dist[u] + w;
                                visited[v] = true;
                                q[++r] = v; 
                        }
                }
        }        
        pos = 1;
        for (i = 2; i <= n; i++)
        {
                if (dist[i] > dist[pos])
                        pos = i;
        }
        return pos;
}

int main() 
{
        
        scanf("%d%d",&n,&m);
        for (i = 1; i <= m; i++)
        {
                scanf("%d%d%d",&u,&v,&w);
                addedge(u,v,w);
                addedge(v,u,w);        
        }
        s = bfs(1,dista);
        t = bfs(s,dista);
        bfs(t,distb);
        ans1 = dista[t];
        for (i = 1; i <= n; i++) ans2 = max(ans2,min(dista[i],distb[i]));
        printf("%lld
",ans1 + ans2);
        
        return 0;
    
}