forked from joy-mollick/Problem-Solving-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
SPOJ BENEFACT - The Benefactor.cpp
68 lines (56 loc) · 1.34 KB
/
SPOJ BENEFACT - The Benefactor.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> ipair;
const int mx=50001;
vector<ipair>adj[mx];
int n;
ll dist[mx]={0};
int shortest_path(int src)
{
priority_queue<ipair,vector<ipair>,greater<ipair> >pq;
bool vis[n+1]={false};
pq.push(make_pair(0,src));
for(int y=1;y<=n;y++) dist[y]=1e9;
dist[src]=0;
while(!pq.empty())
{
int u=pq.top().second;
pq.pop();
if(!vis[u]) vis[u]=true;
else continue;
for(int i=0;i<adj[u].size();i++)
{
int v=adj[u][i].first;
ll weight=adj[u][i].second;
if(weight+dist[u]<dist[v])
{
dist[v]=dist[u]+weight;
pq.push(make_pair(dist[v],v));
}
}
}
ll mx=0;
int id;
for(int k=1;k<=n;k++) {if(mx<dist[k]){mx=dist[k],id=k;}};
return id;
}
int main()
{
int t,a,b;
ll c;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) adj[i].clear();
for(int j=0;j<n-1;j++)
{
cin>>a>>b>>c;
adj[a].push_back(make_pair(b,c));
adj[b].push_back(make_pair(a,c));
}
int y=shortest_path(1);
ll ans=dist[shortest_path(y)];
cout<<ans<<endl;
}
}