poj 1985 Cow Marathon 树的直径

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #define inf 0x7fffffff
 9 using namespace std;
10 const int maxn=40000+10;
11 const int M = 100000+10;
12 
13 int n,m;
14 struct node
15 {
16     int v,w;
17     int next;
18 }edge[M*3];
19 int head[maxn],edgenum;
20 
21 void add(int u,int v,int w)
22 {
23     edge[edgenum].v=v ;edge[edgenum].w=w ;
24     edge[edgenum].next=head[u] ;head[u]=edgenum++ ;
25 
26     edge[edgenum].v=u ;edge[edgenum].w=w ;
27     edge[edgenum].next=head[v] ;head[v]=edgenum++ ;
28 }
29 
30 int d[maxn],vis[maxn];
31 int bfs(int from)
32 {
33     memset(d,-1,sizeof(d));
34     memset(vis,0,sizeof(vis));
35     queue<int> Q;
36     Q.push(from);
37     vis[from]=1 ;d[from]=0 ;
38     int maxlen=-1,k=0;
39     while (!Q.empty())
40     {
41         int u=Q.front() ;Q.pop() ;
42         for (int i=head[u] ;i!=-1 ;i=edge[i].next)
43         {
44             int v=edge[i].v;
45             if (!vis[v])
46             {
47                 vis[v]=1;
48                 d[v]=d[u]+edge[i].w;
49                 Q.push(v);
50                 if (d[v]>maxlen)
51                 {
52                     maxlen=d[v];
53                     k=v;
54                 }
55             }
56         }
57     }
58     return k;
59 }
60 
61 int main()
62 {
63     while (scanf("%d%d",&n,&m)!=EOF)
64     {
65         memset(head,-1,sizeof(head));
66         edgenum=0;
67         int a,b,c;
68         char str[3];
69         for (int i=1 ;i<=m ;i++)
70         {
71             scanf("%d%d%d%s",&a,&b,&c,str);
72             add(a,b,c);
73         }
74         int v=bfs(1);
75         int u=bfs(v);
76         printf("%d\n",d[u]);
77     }
78     return 0;
79 }