#include "dreaming.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using ll = long long; // ??
namespace Solver {
const int MAXN = 1e5;
struct Edge {
int u, cost;
Edge( int u, int cost ): u(u), cost(cost) {}
};
std::vector<Edge> adj[MAXN];
bool viz[MAXN];
int dep[MAXN];
void get_deps( int u, int p ) {
viz[u] = true;
dep[u] = 0;
for( Edge e : adj[u] )
if( e.u != p ){
get_deps( e.u, u );
dep[u] = std::max( dep[u], e.cost + dep[e.u] );
}
}
int min_radius;
int diameter;
void dai_tati( int u, int p, int up = 0 ) {
//printf( "dep = %d | up = %d\n", dep[u], up );
min_radius = std::min( min_radius, std::max( dep[u], up ) );
int max1 = 0, max2 = 0;
for( Edge e : adj[u] )
if( e.u != p ){
int chain = e.cost + dep[e.u];
if( chain >= max1 ){
max2 = max1;
max1 = chain;
}else if( chain >= max2 )
max2 = chain;
}
diameter = std::max( diameter, max1 + max2 );
for( Edge e : adj[u] )
if( e.u != p ){
int chain = e.cost + dep[e.u];
dai_tati( e.u, u, e.cost + std::max( up, (max1 == chain) ? max2 : max1 ) );
}
}
// raza, diametru
std::pair<int, int> rezolva_arbore( int root ) {
get_deps( root, root ); // seteaza viz[] si gaseste adancimile
min_radius = +1e9;
diameter = 0;
dai_tati( root, root ); // eu prea lenes sa fac un singur dfs
return std::make_pair( min_radius, diameter );
}
int travelTime( int N, int M, int L, int A[], int B[], int T[] ){
for( int i = 0; i < N; i++ ){
viz[i] = false;
adj[i].clear();
}
for( int i = 0; i < M; i++ ){
adj[A[i]].emplace_back( B[i], T[i] );
adj[B[i]].emplace_back( A[i], T[i] );
}
int biggest_d = 0;
std::vector<int> comps;
for( int i = 0; i < N; i++ )
if( !viz[i] ){
auto comp = rezolva_arbore( i );
comps.push_back( comp.first );
biggest_d = std::max( biggest_d, comp.second );
}
// trebuie sa facem arbore partial de diametru minim cu comps[]
std::sort( comps.begin(), comps.end(), std::greater<int>() );
// sigur se poate max(comps[0] + L + comps[1], comps[1] + 2L + comps[2])
// 0--1, 0--2, 0--3, ..., 0--(n-1)
// NU SE POATE MAI BINE!
// daca nu iei 0--1 esti doar prost
// daca nu e muchie de la 0 la 2 => dist(0, 2) >= 2L deci minim comps[0] + 2L + comps[2] >= comps[1] + 2L + comps[2]
// clar avem 0--1 si 0--2 => raspunsul este minim cel propus la inceput => acela e raspunsul
// printf( "%d comps:", (int)comps.size() );
// for( int x : comps )
// printf( " %d", x );
// printf( "\n" );
if( (int)comps.size() <= 1 )
return std::max( biggest_d, comps.front() );
if( (int)comps.size() <= 2 )
return std::max( biggest_d, comps[0] + L + comps[1] );
return std::max( biggest_d, std::max( comps[0] + L + comps[1], comps[1] + 2 * L + comps[2] ) );
}
}
int travelTime( int N, int M, int L, int A[], int B[], int T[] ){
return Solver::travelTime( N, M, L, A, B, T );
}
