#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 1e5 + 5;
bool visited[maxn] = { 0 };
int dist[maxn] = { 0 }; // Max distance to another node
basic_string <pii> adj[maxn];
pii fnd_furthest(int p, int parent)
{
// cout << p << "\n";
visited[p] = true;
pii maxd = pii(p, 0);
pii a;
for (const pii &i : adj[p])
{
// cout << p << " " << i.first << "\n";
if (i.first == parent) continue;
a = fnd_furthest(i.first, p);
a.second += i.second;
if (a.second > maxd.second) {
maxd = a;
}
}
dist[p] = max(dist[p], maxd.second);
return maxd;
}
// Finds the node in the component with the minimal maximum distance
int fnd_min_max_dist(int p, int parent)
{
int mind = dist[p];
for (pii &i : adj[p])
{
if (i.first == parent) continue;
if (dist[i.first] >= mind || dist[i.first] == 0) continue;
mind = fnd_min_max_dist(i.first, p);
}
return mind;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int n = N, m = M;
for (int i = 0; i < m; i++)
{
adj[A[i]].push_back(pii(B[i], T[i]));
adj[B[i]].push_back(pii(A[i], T[i]));
}
vector <int> distances;
int max_comp = 0;
int components = 0;
pii a, b;
for (int i = 0; i < n; i++)
{
if (!visited[i])
{
components ++;
a = fnd_furthest(i, -1);
b = fnd_furthest(a.first, -1);
a = fnd_furthest(b.first, -1);
// cout << a.first << " " << b.first << " " << a.second << " " << fnd_min_max_dist(a.first, -1) << "\n";
// We have now the diameter by a, b
max_comp = max(max_comp, a.second);
distances.emplace_back(fnd_min_max_dist(a.first, -1));
}
}
// for (int i = 0; i < n; i++) cout << dist[i] << " ";
// cout << "\n";
sort(distances.begin(), distances.end(), greater<int>());
if (components == 1)
{
return max_comp;
}
if (components == 2)
{
return max({max_comp, distances[0] + distances[1] + L});
}
return max({max_comp, distances[0] + distances[1] + L, distances[2] + distances[1] + 2 * L});
}
