#include <vector>
#include <algorithm>
#include "dreaming.h"
using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];
bool visited[MAXN];
int max_d, farthest_node;
int parent_node[MAXN], edge_to_parent[MAXN];
// Standard DFS to find the farthest node and distances
void dfs(int u, int p, int d) {
visited[u] = true;
parent_node[u] = p;
if (d > max_d) {
max_d = d;
farthest_node = u;
}
for (auto& edge : adj[u]) {
int v = edge.first;
int w = edge.second;
if (v != p) {
edge_to_parent[v] = w;
dfs(v, u, d + w);
}
}
}
int get_min_max_dist(int start_node, int& component_diameter) {
max_d = -1;
dfs(start_node, -1, 0);
int u = farthest_node;
max_d = -1;
dfs(u, -1, 0);
int v = farthest_node;
component_diameter = max_d;
// Path from v back to u to find the center
int curr = v;
int dist_from_v = 0;
int min_max_d = max_d; // Start with diameter
while (curr != -1) {
// The distance to the farthest end is max(dist_from_v, diameter - dist_from_v)
min_max_d = min(min_max_d, max(dist_from_v, max_d - dist_from_v));
if (curr == u) break;
dist_from_v += edge_to_parent[curr];
curr = parent_node[curr];
}
return min_max_d;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++) {
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
vector<int> radii;
int overall_max_diameter = 0;
for (int i = 0; i < N; i++) {
if (!visited[i]) {
int comp_diam = 0;
radii.push_back(get_min_max_dist(i, comp_diam));
overall_max_diameter = max(overall_max_diameter, comp_diam);
}
}
sort(radii.rbegin(), radii.rend());
// Case with 2 components (Subtask 3)
if (radii.size() >= 2) {
overall_max_diameter = max(overall_max_diameter, radii[0] + radii[1] + L);
}
// Case with 3 or more components (General case)
if (radii.size() >= 3) {
overall_max_diameter = max(overall_max_diameter, radii[1] + radii[2] + 2 * L);
}
return overall_max_diameter;
}
