Farthest Node Problem-II LightOJ

//Bismillahir Rahmanir Rahim

#include<bits/stdc++.h>

#define output() freopen("out.txt","w",stdout)
#define pii pair<int,long>
#define MAX 30010

using namespace std;

vector<pii>edge[MAX];
queue<long> q;
vector<bool>visited;
vector<long> dist;

long BFS(int s,int n){
    q.push(s);

    for(int i=0;i<n;i++){
        visited.push_back(false);
        dist.push_back(0);
    }

    visited[s]=true;
    dist[s]=0;
    long m=-1;
    while(!q.empty()){
        int top = q.front();

        int sz = edge[top].size();

        for(int i=0;i<sz;i++){
            pii k= edge[top][i];
            int a=k.first;
            long w=k.second;

            if(!visited[a]){
                q.push(a);
                visited[a]=true;
                dist[a]=dist[top]+w;
                if(dist[a]>m){
                    m=dist[a];
                }
            }
        }
        q.pop();
    }
    if(!q.empty()){
        queue<long> e;
        swap(q,e);
    }

    dist.clear();
    visited.clear();

    return m;
}


int main(){
    int test;
    scanf("%d",&test);
    int counter=1;
    while(test--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n-1;i++){
            int s,d;
            long w;
            scanf("%d%d%ld",&s,&d,&w);
            edge[s].push_back(pii(d,w));
            edge[d].push_back(pii(s,w));
        }

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

        for(int i=0;i<n;i++){
            long res= BFS(i,n);
            printf("%ld\n",res);
        }

        for(int i=0;i<n;i++) edge[i].clear();
    }
    return 0;
}