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();
        }

    }

}

1094 - Farthest Nodes in a Tree

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

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 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;
    }
};

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);
        ans=dis[ans];



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


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

    }
}

1002 - Country Roads

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

Solution :

#include<bits/stdc++.h>
#define inf 100000

using namespace std;

vector<int> v[600],cost[600];

int dis[600];


struct node
{
    int city,dist;

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

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

void dijkstra(int s)
{

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

    dis[s]=0;

    priority_queue<node>q;

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

    while(!q.empty())
    {

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

        int u=t.city;

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

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

            }
        }
    }

}

int main()
{



    int n,e,t,a,b,c,s;
    scanf("%d",&t);

for(int ca=1;ca<=t;ca++)

  {

scanf("%d%d",&n,&e);


    for(int i=1;i<=e;i++)
    {
        scanf("%d%d%d",&a,&b,&c);

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

    scanf("%d",&s);



    dijkstra(s);

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

    for(int i=0;i<n;i++)
    {
        if(dis[i]==inf) printf("Impossible\n");
        else printf("%d\n",dis[i]);
    }

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

  }

}