Light OJ 1094 – Farthest Nodes in a Tree

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1094


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

vector<int>edge[30010];
vector<int>cost[30010];
int n,point1,point2,ans,v1;
bool visited[30010];
int d[30010];
void bfs(int src)
{
    visited[src]=1;
    d[src]=0;
    queue<int>Q;
    Q.push(src);

    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        if(d[u]>v1)
        {
            v1=d[u];
            point1=u;
        }

        for(int i=0;i<SZ(edge[u]);i++)
        {
            int v=edge[u][i];
            if(d[v]<d[u]+cost[u][i] && !visited[v])
            {
                d[v]=d[u]+cost[u][i];
                Q.push(v);
                visited[v]=1;
            }
        }
    }
}

void allclear(int n)
{
    loop(i,n+5)
    {
        edge[i].clear();
        cost[i].clear();
        d[i]=0;
        visited[i]=0;
    }
    v1=-1;
}
int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        sf(n);
        allclear(n);
        loop(i,n-1)
        {
            int u,v,w;
            sfff(u,v,w);
            edge[u].pb(v);
            edge[v].pb(u);
            cost[u].pb(w);
            cost[v].pb(w);
        }
        bfs(0);
        loop(i,n+5)
       {
          d[i]=0;
          visited[i]=0;
       }
        v1=-1;
        bfs(point1);
        PRINT_CASE;
        pf("%d\n",v1);
    }
    return 0;
}

IDEA :

BFS from node ‘0’ (or any other node) to find the farthest node from ‘0’. Call it ‘u’
BFS from node ‘u’ to find the farthest node from ‘u’. Call it ‘v’
The distance from ‘u’ to ‘v’ is the maximum distance in the tree.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s