Tranvick

Untitled

Nov 15th, 2011
204
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include <cstdio>
  2. #define N 66666
  3.  
  4. long long n,ef[N],es[N],ev[N],first[N],next[N],c,m,dest[N];
  5. bool b[N];
  6.  
  7. void add(int x,int y,int z)
  8. {
  9.     next[++c]=first[x];
  10.     first[x]=c;
  11.     ef[c]=x;es[c]=y;ev[c]=z;
  12. }
  13.  
  14. void init(void)
  15. {
  16.     freopen("input.txt","r",stdin);
  17.     freopen("output.txt","w",stdout);
  18.     scanf("%I64d",&n);
  19.     long long v1,v2,vv;
  20.     c=0;
  21.     for (int i=1;i<n;i++)
  22.     {    
  23.         scanf("%I64d %I64d %I64d",&v1,&v2,&vv);
  24.         add(v1,v2,vv);
  25.         add(v2,v1,vv);
  26.     }
  27.     m=c;
  28. }
  29.    
  30. void dfs(int v)
  31. {
  32.     b[v]=true;
  33.     long long h;
  34.     for (h=first[v];h;h=next[h])
  35.     {
  36.         if (!b[es[h]])
  37.         {
  38.             dest[es[h]]=dest[v]+ev[h];
  39.             dfs(es[h]);
  40.         }
  41.     }
  42. }
  43.  
  44. void sol(void)
  45. {
  46.     dest[1]=0;
  47.     dfs(1);
  48.     long long i,fmax=0;
  49.     dest[0]=-1000000;
  50.     for (i=1;i<=n;i++)
  51.         if (dest[i]>dest[fmax])
  52.             fmax=i;
  53.     dest[fmax]=0;
  54.     for (i=1;i<=n;i++)
  55.         b[i]=false;
  56.     dfs(fmax);
  57.     dest[0]=-1000000;fmax=0;
  58.     for (i=1;i<=n;i++)
  59.         if (dest[i]>dest[fmax])
  60.             fmax=i;
  61.     printf("%I64d",dest[fmax]);
  62. }
  63.  
  64. int main(void)
  65. {
  66.     init();
  67.     sol();
  68.     return 0;
  69. }
  70.  
  71.  
Advertisement
Add Comment
Please, Sign In to add comment