# include "dreaming.h"
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
const long long NN = 1e5 + 100;
vector < pair < long long, long long > > gr[NN];
vector < pair < long long, long long > > cent;
bool used[NN];
long long d[NN], p[NN], mx, u;
void dfs( long long v, long long f )
{
used[v] = true;
for ( auto to: gr[v] ){
if( to.first == f )
continue;
else{
d[to.first] = d[v] + to.second;
p[to.first] = v;
if( mx < d[to.first] ){
mx = d[to.first];
u = to.first;
}
dfs( to.first, v );
}
}
}
pair < long long, long long > getCenter( long long v, long long N )
{
mx = u = 0;
d[v] = 0;
dfs( v, -1 );
if( u == 0 )
return {0, 0};
v = u;
d[v] = mx = u = 0;
dfs( v, - 1 );
long long D = mx;
long long mn = 2e9;
while( u != v ){
if( d[u] >= (D + 1) / 2 )
mn = min( mn, d[u] );
if( (D - d[u]) >= (D + 1) / 2 )
mn = min( mn, D - d[u] );
u = p[u];
}
return {mn, D};
}
long long travelTime( long long N, long long M, long long L, long long A[], long long B[], long long T[] )
{
for ( long long i = 1; i <= M; i ++ ){
A[i] ++; B[i] ++;
gr[A[i]].push_back( {B[i], T[i]} );
gr[B[i]].push_back( {A[i], T[i]} );
}
fill( used, used + N + 1, false );
for ( long long i = 1; i <= N; i ++ ){
if( used[i] == 0 ){
cent.push_back( getCenter(i, N ) );
}
}
sort( cent.begin(), cent.end() );
reverse( cent.begin(), cent.end() );
long long answer = 0;
for ( auto c: cent )
answer = max( answer, c.second );
if( M == N - 1 ){
return cent[0].second;
}
else if ( M == N - 2 ){
return max( answer, cent[0].first + cent[1].first + L ) ;
}
else {
return max( max( cent[0].first + cent[1].first + L, cent[1].first + cent[2].first + 2 * L ), answer );
}
}
/*
int main()
{
long long n, m, l;
long long a[NN] = {}, b[NN] = {}, t[NN] = {};
cin >> n >> m >> l;
for ( long long i = 1; i <= m; i ++ ){
cin >> a[i] >> b[i] >> t[i];
}
cout << travelTime( n, m, l, a, b, t );
return 0;
}
8 7 100
0 1 4
1 3 2
1 2 1
1 4 4
3 5 3
3 6 4
2 7 6
4 2 50
0 1 100
1 2 100
7 3 1
0 1 4
2 3 4
4 5 4
*/
Compilation message
/tmp/ccoUDDbe.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
