LightOJ 1094 Solution

on

#include<bits/stdc++.h>
#define N 30000
#define White 1
#define Gray 2
#define Black 3
#define ll long long
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int node, edge, color[N], parent[N];
ll dis[N];

vector<int>adj[30000], weight[30000];

ll maximum_indx(int pointer)
{
    ll mx_value = 0, indx = -1;
    for(int i=0; i<node; i++)
    {
        if(mx_value < dis[i])
        {
            mx_value = dis[i];
            indx = i;
        }
    }

    if(pointer == 0)
        return indx;
    else
        return mx_value;
}

void bfs(int StartNode)
{
    for(int i=0; i<node; i++)
    {
        color[i] = White;
        dis[i] = INT_MIN;
        parent[i] = -1;
    }

    dis[StartNode] = 0;
    parent[StartNode] = -1;
    color[StartNode] = Black;

    queue<int>q;
    q.push(StartNode);

    while(!q.empty())
    {
        int x = q.front();
        q.pop();

        for(int i=0; i<adj[x].size(); i++)
        {
            int nd = adj[x][i];

            if(color[nd] == White)
            {
                dis[nd] = dis[x] + weight[x][i];
                q.push(nd);

                color[nd] = Black;
            }
        }
    }

}

void clears()
{
    for(int i=0; i<N; i++)
    {
        adj[i].clear();
        weight[i].clear();
    }
}

int main()
{
    fastio

    int t;
    cin >> t;

    int k = 1;

    while(t--)
    {
        cin >> node;

        int n1, n2, w;

        for(int i=1; i<node; i++)
        {
            cin >> n1 >> n2 >> w;
            adj[n1].push_back(n2);
            adj[n2].push_back(n1);

            weight[n1].push_back(w);
            weight[n2].push_back(w);
        }

        bfs(0);

        int first_node = maximum_indx(0);

        bfs(first_node);

        ll maximum_value = maximum_indx(1);

        cout << "Case " << k++ << ": " << maximum_value << "\n";

        clears();
    }

    return 0;
}

Comments

Post a Comment