#include <bits/stdc++.h>
#include "dreaming.h"
#define MAXN 100000
using namespace std;
typedef long long ll;
vector<pair<ll, ll>> nodi[MAXN];
vector<bool> proc;
vector<ll> dist;
void dfs(ll v, vector<ll>& gruppo)
{
proc[v] = true;
gruppo.push_back(v);
for (auto [u, w]: nodi[v])
{
if (!proc[u])
{
dist[u] = dist[v] + w;
dfs(u, gruppo);
}
}
}
void dfs2(ll v)
{
proc[v] = true;
for (auto [u, w]: nodi[v])
{
if (!proc[u])
{
dist[u] = dist[v] + w;
dfs2(u);
}
}
}
bool dfs3(ll v, ll p, ll y, vector<ll>& diam)
{
if (v == y)
return true;
bool ok = false;
for (auto [u, w]: nodi[v])
{
if (u != p)
{
if (dfs3(u, v, y, diam))
{
ok = true;
diam.push_back(w);
break;
}
}
}
return ok;
}
vector<ll> trova_diametro(ll v)
{
vector<ll> gruppo;
dist[v] = 0;
dfs(v, gruppo);
sort(gruppo.begin(), gruppo.end(), [&](ll a, ll b){return dist[a] > dist[b];});
for (ll i: gruppo)
proc[i] = false;
ll x, y;
x = gruppo[0];
dist[x] = 0;
dfs2(x);
sort(gruppo.begin(), gruppo.end(), [&](ll a, ll b){return dist[a] > dist[b];});
y = gruppo[0];
vector<ll> diam;
dfs3(x, -1, y, diam);
return diam;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (ll i = 0; i < M; i++)
{
nodi[A[i]].push_back({B[i], T[i]});
nodi[B[i]].push_back({A[i], T[i]});
}
vector<ll> valori;
vector<ll> diam;
dist.resize(N, 0);
proc.resize(N, false);
for (ll i = 0; i < N; i++)
{
if (!proc[i])
{
vector<ll> diametro = trova_diametro(i);
/*
cout << "\n\n";
for (ll i: diametro)
cout << i << " ";
cout << "\n\n";
*/
if (diametro.empty())
{
valori.push_back(0);
diam.push_back(0);
continue;
}
ll sx = 0, dx = 0;
for (ll j: diametro)
dx += j;
ll minimo = dx;
diam.push_back(dx);
for (ll j = 0; j < diametro.size(); j++)
{
sx += diametro[j];
dx -= diametro[j];
minimo = min(minimo, max(sx, dx));
}
valori.push_back(minimo);
}
}
sort(valori.begin(), valori.end());
sort(diam.begin(), diam.end());
return max(diam.back(), valori.back() + valori[valori.size() - 2] + L);
if (valori.size() == 1)
return diam[0];
if (valori.size() == 2)
return max(diam[1], valori[0] + valori[1] + L);
if (valori.size() > 2)
return max(max(diam.back(), valori.back() + valori[valori.size() - 2] + L), valori[valori.size() - 2] + valori[valori.size() - 3] + 2 * L);
}
