1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| #include<stdio.h> #include<queue> #include<string.h> using namespace std; struct { int u,v,w,next; }edge[10001]; int vis[10001]; int d[10001]; int head[10001]; int cnt,j,ans; void add(int u,int v,int w) { edge[cnt].u=u; edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;
} void bfs(int x) { memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); vis[x]=1; queue<int>que; que.push(x); while(!que.empty()) { int xx=que.front(); que.pop(); for(int i=head[xx];i!=-1;i=edge[i].next) { int vv=edge[i].v; if(!vis[vv]&&d[vv]<d[xx]+edge[i].w) { vis[vv]=1; d[vv]=d[xx]+edge[i].w; if(d[vv]>ans) { ans=d[vv]; j=vv; } que.push(vv); } } } } int main() { int u,v,w; memset(head,-1,sizeof(head)); while(~scanf("%d%d%d",&u,&v,&w)) { add(u,v,w);add(v,u,w); } ans=0,cnt=0; bfs(1); bfs(j); printf("%d\n",ans); return 0; }
|