#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N=100000; int n,m; int head[N]; struct Node { int v,w,next; }edge[N]; int cnt=0; void addedge(int u,int v,int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } int vis[N]; int dis[N]; int q[N]; int res; int bfs(int u) { memset(vis,0,sizeof(vis)); int front=0; int rear=1; q[1]=u; vis[u]=1; dis[u]=0; int ans=0; while(front < rear) { front++; int tmp = q[front]; for(int i=head[tmp];i!=-1;i=edge[i].next) { int v=edge[i].v; if(!vis[v]) { rear++; q[rear]=v; vis[v]=1; dis[v]=dis[tmp]+edge[i].w; if(dis[v]>ans) { ans=dis[v]; res=v; } } } } return ans; } int main() { int u,v,w; char ch; while(~scanf("%d%d",&n,&m)) { memset(head,-1,sizeof(head)); cnt=0; for(int i=0;i<m;i++) { scanf("%d %d %d %c",&u,&v,&w,&ch); addedge(u,v,w); addedge(v,u,w); } bfs(1); printf("%d\n",bfs(res)); } return 0; } |
Double click to view unformatted code.