- #include
- #include
- #include
- using namespace std;
- int
- n,m,x,y,z,head[
- 40002
- ],dad[
- 40002
- ],dis[
- 40003],maxx,maxn,sumedge;
- struct Edge
- {
- int x,y,z,nxt;
- Edge(int
- x=
- 0
- ,
- int
- y=
- 0
- ,
- int
- z=
- 0
- ,
- int
- nxt=
- 0):
- x(x),y(y),z(z),nxt(nxt){}
- }edge[80009];
- void
- add(
- int
- x,
- int
- y,
- int z)
- {
- edge[
- ++sumedge]=
- Edge(x,y,z,head[x]);
- head[x]
- =
- sumedge;
- }
- void
- dfs(
- int x)
- {
- for
- (
- int
- i=head[x];i;i=
- edge[i].nxt)
- {
- int
- v=
- edge[i].y;
- if
- (dad[x]!=
- v)
- {
- dad[v]
- =
- x;
- dis[v]
- =dis[x]+
- edge[i].z;
- dfs(v);
- }
- }
- }
- int main()
- {
- scanf("%d%d"
- ,&n,&
- m);
- for
- (
- int
- i=
- 1
- ;i<=m;i++
- )
- {
- char
- s[
- 4];
- cin
- >>x>>y>>z>>s[
- 0];
- add(x,y,z);
- add(y,x,z);
- }
- dfs(1);
- maxx
- =-
- 0x7fffff;
- for
- (
- int
- i=
- 1
- ;i<=n;i++
- )
- {
- if
- (dis[i]>
- maxx)
- {
- maxx
- =
- dis[i];
- maxn
- =
- i;
- }
- }
- memset(dis,0
- ,
- sizeof(dis));
- memset(dad,0
- ,
- sizeof(dad));
- dfs(maxn);
- maxx
- =-
- 0x7fff;
- for
- (
- int
- i=
- 1
- ;i<=n;i++
- )
- {
- if
- (dis[i]>
- maxx)
- {
- maxx
- =
- dis[i];
- }
- }
- printf("%d\n",maxx);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2213525.html