#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector< pair<int, int> > Graph[100009];
vector< bool > v(100009, false);
vector< int > ans(100009);
int Maxi = 0;
int maxi = -1;
int Last = 0;
void DFS(int node, int last, int dist){
// cout << node << ' ' << last << endl;
if(dist > Maxi){
Maxi = dist;
Last = node;
}
v[node] = true;
for(auto a : Graph[node]){
if(a.first != last){
DFS(a.first, node,dist+a.second);
}
}
}
vector<int> diste(100009);
int radius;
void Radius(int node, int last, int dist){
diste[node] = max(diste[node], dist);
for(auto a : Graph[node]){
if(a.first != last){
Radius(a.first, node, dist+a.second);
}
}
}
void R(int node, int last, int dist, int diam){
radius = min(radius, max(dist, diste[node]));
for(auto a : Graph[node]){
if(a.first != last){
R(a.first, node, dist+a.second, diam);
}
}
}
int F(int a){
// cout << a << endl;
Maxi = -1;
DFS(a,-1,0);
int A = Last;
// cout << A << endl;
Maxi = -1;
DFS(A,-1,0);
//cout << A << ' ' << "Diameter " << Maxi << endl;
maxi = max(Maxi, maxi);
int B = Last;
int diam = Maxi;
//cout << "Between node " << A << " and " << B << ' ' << diam << endl;
Radius(A, -1,0);
radius = 9999999999999;
R(B,-1,0,diam);
//cout << radius << endl;
return radius;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; i++){
Graph[A[i]].push_back(make_pair(B[i], T[i]));
Graph[B[i]].push_back(make_pair(A[i], T[i]));
}
int t = 0;
for(int i = 0; i < N; i++){
if(!v[i]){
ans[t++] = F(i);//FUNCTION
}
}
for(int i = 0; i < 100009; i++){
diste[i] = -1;
}
sort(ans.begin(), ans.begin()+t);
reverse(ans.begin(), ans.begin()+t);
/*for(int i = 0; i < t; i++){
cout << ans[i] << ' ';
}
cout << endl;*/
if(t > 1){
maxi = max(maxi, ans[0]+ans[1]+L);
if(t > 2){
maxi = max(maxi, ans[1]+ans[2]+2*L);
}
}
return maxi;
}
/*
signed main(){
int n, m, l;
cin >> n >> m >> l;
int a[m];
int b[m];
int t[m];
for(int i = 0; i < m; i++){
cin >> a[i] >> b[i] >> t[i];
}
cout << travelTime(n,m,l,a,b,t) << endl;
}*/
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
4 2 1
0 1 1
2 3 2
*/
Compilation message
/tmp/ccvVegZ5.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
