1257 - Farthest Nodes in a Tree (II)

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

Solution :


#include<bits/stdc++.h>
#define inf 1e9
#define ll long long

using namespace std;

vector<ll int> v[30005],cost[30005];

ll int dis[30005];
ll int dis1[30005];
ll int n;



struct node
{
    ll int city,dist;

    node(ll int a,ll int b)
    {
        city=a;
        dist=b;
    }

    bool operator <(const node &p)const
    {
        return p.dist<dist;
    }
};

void func(ll int s)
{

    for(ll int i=0; i<30005; i++) dis1[i]=inf;

    ll int mx=-1,p;

    dis1[s]=0;
    priority_queue<node>q;

    q.push(node(s,0));

    while(!q.empty())
    {

        node t=q.top();
        q.pop();

        ll int u=t.city;

        for(ll int i=0; i<v[u].size(); i++)
        {
            ll int p=v[u][i];

            if(dis1[p]>(dis1[u]+cost[u][i]))
            {
                dis1[p]=(dis1[u]+cost[u][i]);
                q.push(node(p,dis1[p]));

            }
        }
    }



}
ll int dijkstra(ll int s)
{

    for(ll int i=0; i<30005; i++) dis[i]=inf;

    ll int mx=-1,p;

    dis[s]=0;
    priority_queue<node>q;

    q.push(node(s,0));

    while(!q.empty())
    {

        node t=q.top();
        q.pop();

        ll int u=t.city;

        for(ll int i=0; i<v[u].size(); i++)
        {
            ll int p=v[u][i];

            if(dis[p]>(dis[u]+cost[u][i]))
            {
                dis[p]=(dis[u]+cost[u][i]);
                q.push(node(p,dis[p]));

            }
        }
    }
    for(ll int i=0; i<n; i++)
    {
        if(dis[i]>mx)
        {
            mx=dis[i];
            p=i;
        }
    }


    return p;


}
int main()
{


    ll int t,a,b,c,ans=0,s=0,mx;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        s=0,mx=-1,ans=0;


        for(ll int i=0; i<n-1; i++)
        {

            scanf("%lld%lld%lld",&a,&b,&c);



            v[a].push_back(b);
            v[b].push_back(a);
            cost[a].push_back(c);
            cost[b].push_back(c);

        }


        ans=dijkstra(1);
        ans=dijkstra(ans);
        func(ans);

        printf("Case %lld:\n",ca);

       for(int i=0;i<n;i++)
       {
           printf("%lld\n",max(dis[i],dis1[i]));
       }


        for(ll int i=0; i<30005; i++)
        {
            v[i].clear();
            cost[i].clear();
        }

    }

}