樹的直徑模闆題：poj1985

​​題目連結：樹的直徑​​

題解：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1e5+5;
struct node
{
    int to,w,nex;
} tr[maxn];
//樹的直徑
int head[maxn];
int dis[maxn],vis[maxn],n,cnt,pp,in[maxn];
void add(int u,int v,int w)
{
    tr[cnt].to=v;
    tr[cnt].w=w;
    tr[cnt].nex=head[u];
    head[u]=cnt++;
}
void bfs(int root)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    int minx=-1;
    queue<int>q;
    dis[root]=0;
    q.push(root);
    vis[root]=1;
    while(!q.empty())
    {
        //printf("1\n");
        int u=q.front();
        q.pop();
        for(int i=head[u]; ~i; i=tr[i].nex)
        {
            int v=tr[i].to;
            int w=tr[i].w;

            if(!vis[v])
            {
                q.push(v);
                vis[v]=1;
                dis[v]=dis[u]+w;
                if(dis[v]>minx)
                {
                    minx=dis[v];
                    pp=v;
                }
            }
        }
    }
}
int main()
{
    int m;
    scanf("%d %d",&n,&m);
    char s[10];
    int u,v,w,sum=0;
    memset(head,-1,sizeof(head));
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d %d %s",&u,&v,&w,s);
        add(u,v,w);
        add(v,u,w);
    }
    bfs(1);
    bfs(pp);
    int maxx2=dis[pp];
    printf("%d\n",maxx2);
}