fork download
copy 
  1.     // Praney Rai
  2.     // Welcome (:
  3.     #include <stdio.h>
  4.     #include <bits/stdc++.h>
  5.     using namespace std;
  6.  
  7.     #define rep(i , n)	for(ll i=0 ; i<n ; ++i)
  8.     #define loop(i , a , b)	for(ll i=a ; i<b ; ++i)
  9.     #define loopi(i , a) for(auto i = a.begin() ; i != a.end() ; ++i)
  10.     #define io freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  11.     #define Max(a, b)	(a > b ? a : b)
  12.     #define Min(a, b)	(a > b ? b : a)
  13.     #define Mid(a, b)	((a+b)/2)
  14.     #define all(x) x.begin(), x.end()
  15.     #define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  16.     #define rtn return
  17.     #define xx first
  18.     #define yy second
  19.     #define pb push_back
  20.     #define mp make_pair
  21.     #define eb emplace_back
  22.     #define fill(a , x) memset(a , x , sizeof(a))
  23.  
  24.     typedef long long ll;
  25.     typedef string str;
  26.     typedef double db;
  27.     typedef vector<ll> vi;
  28.  
  29.     const int N = 100100;
  30.     const int MOD = int(1e9) + 7;
  31.     const ll INF = 1e18;
  32.     const db PI = 3.1415926536;
  33.  
  34.     ll vis[50050];
  35.  
  36.     int main() {
  37.     	std::ios_base::sync_with_stdio(false);
  38.     	std::cin.tie(NULL);
  39.     	std::cout.tie(NULL);
  40.     	ll n = 0, m = 0, k = 0, lo = 0, hi = 0, mi = INF, mx = -INF, sum = 0, ans = 0, cnt=0, t = 0, v1 = 0, v2 = 0;
  41.     	str s, s1, s2;
  42.     	char c, c1, c2, *ptr;
  43.     	db dub=0;
  44.     	/////////////////////////////////////////////////////////////////////////////////////////////
  45.     	cin >> t;
  46.     	while (t--) {
  47.     		cin >> n;
  48.     		list<int> add[50050];
  49.     		map<ll, map<ll, ll> > cst;
  50.     		for (int i = 0; i < n - 1; i++) {
  51.     			int a, b, c;
  52.     			cin >> a >> b >> c;
  53.     			add[a].pb(b);
  54.     			add[b].pb(a);
  55.     			if (a < b) {
  56.     				cst[a][b] = c;
  57.     			}
  58.     			else {
  59.     				cst[b][a] = c;
  60.     			}
  61.     		}
  62.     		queue<int> q;
  63.     		q.push(1);
  64.     		fill(vis, 0);
  65.     		vis[1] = 0;
  66.     		while (!q.empty()) {
  67.     			int x  = q.front();
  68.     			q.pop();
  69.     			for (auto i : add[x]) {
  70.     				if (vis[i] == 0) {
  71.     					if (x < i) {
  72.     						vis[i] = vis[x] + cst[x][i];
  73.     					}
  74.     					else {
  75.     						vis[i] = vis[x] + cst[i][x];
  76.     					}
  77.     					q.push(i);
  78.     				}
  79.     			}
  80.     		}
  81.     		mx = -INF, v1 = 0;
  82.     		loop (i, 1, n+1) {
  83.     			if (vis[i] > mx) {
  84.     				mx = vis[i];
  85.     				v1 = i;
  86.     			}
  87.     		}
  88.     		q.push(v1);
  89.     		fill(vis, 0);
  90.     		vis[v1] = 0;
  91.     		while (!q.empty()) {
  92.     			int x  = q.front();
  93.     			q.pop();
  94.     			for (auto i : add[x]) {
  95.     				if (vis[i] == 0) {
  96.     					if (x < i) {
  97.     						vis[i] = vis[x] + cst[x][i];
  98.     					}
  99.     					else {
  100.     						vis[i] = vis[x] + cst[i][x];
  101.     					}
  102.     					q.push(i);
  103.     				}
  104.     			}
  105.     		}
  106.     		mx = -INF;
  107.     		loop (i, 1, n+1) {
  108.     			if (vis[i] > mx) {
  109.     				mx = vis[i];
  110.     			}
  111.     		}
  112.     		cout << mx << '\n';
  113.     	}
  114.  
  115.  
  116.     }
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/s1a1y1
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!