1 //Accepted    492 KB    0 ms 2 //树的直径 bfs 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <queue> 7 using namespace std; 8 const int imax_n = 10005; 9 struct node10 {11     int u,v,c;12     node()13     {14 15     }16     node(int u,int v,int c):u(u),v(v),c(c)17     {18 19     }20 }p[2*imax_n];21 int e;22 int head[imax_n];23 int next[imax_n*2];24 void addEdge(int u,int v,int c)25 {26     p[e]=node(u,v,c);27     next[e]=head[u];28     head[u]=e++;29 }30 void init()31 {32     memset(head,-1,sizeof(head));33     memset(next,-1,sizeof(next));34     e=0;35 }36 bool vis[imax_n];37 int dis[imax_n];38 queue<int >q;39 int bfs(int s)40 {41     int ans=0;42     int temp_node;43     while (!q.empty()) q.pop();44     memset(vis,0,sizeof(vis));45     q.push(s);46     vis[s]=1;47     memset(dis,0,sizeof(dis));48     while (!q.empty())49     {50         int x=q.front();51         q.pop();52         if (dis[x]>ans)53         {54             ans=dis[x];55             temp_node=x;56         }57         for (int i=head[x];i+1;i=next[i])58         {59             int y=p[i].v;60             if (!vis[y])61             {62                 vis[y]=1;63                 q.push(y);64                 if (dis[x]+p[i].c>dis[y])65                 dis[y]=dis[x]+p[i].c;66             }67         }68     }69     return temp_node;70 }71 int main()72 {73     int x,y,c;74     init();75     while (scanf("%d%d%d",&x,&y,&c)!=EOF)76     //for (int i=0;i<5;i++)77     {78         //scanf("%d%d%d",&x,&y,&c);79         addEdge(x,y,c);80         addEdge(y,x,c);81     }82     x=bfs(1);83     y=bfs(x);84     printf("%d\n",dis[y]);85     return 0;86 }