1509: [NOI2003]逃学的小孩

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 447  Solved: 240

[][][]

Description

Input

第一行是两个整数N（3  N  200000）和M，分别表示居住点总数和街道总数。以下M行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1Ui, Vi  N，1  Ti  1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。街道信息不会重复给出。

Output

仅包含整数T，即最坏情况下Chris的父母需要花费T分钟才能找到Chris。

Sample Input

4 3

1 2 1

2 3 1

3 4 1

Sample Output

4

HINT

 

Source

 

本题就是求在树上 MAX(dis[A,B]+MIN(dis[A,C]+dis[B,C]))

可以证明AB是树上最长链

 

BFS求树直径。。。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;vector
              
                e[200005],w[200005];int n,m;long long dista[200005],distb[200005];bool vis[200005];int bfs(int u,long long dist[]){ long long ret=0; int pos=0; memset(vis,0,sizeof(vis)); dist[u]=0; queue
               
                 q; q.push(u); vis[u]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i
                
                 ret) { pos=v; ret=dist[v]; } } } return pos;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); e[x].push_back(y); e[y].push_back(x); w[x].push_back(z); w[y].push_back(z); } int a=bfs(1,dista); int b=bfs(a,dista); bfs(b,distb); long long ans=0; for(int i=1;i<=n;i++) ans=max(ans,min(dista[i],distb[i])); ans+=distb[a]; printf("%lld\n",ans); return 0;}