#include "dreaming.h"
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN], merged_adj[MAXN];
int d[MAXN], vis_merged[MAXN];
bool vis[MAXN];
vector<int> nodes;
void dfs_ecc(int u, int p, int dist, int* dist_arr) {
dist_arr[u] = dist;
vis[u] = true;
nodes.push_back(u);
for (auto &e : adj[u]) if (e.first != p) dfs_ecc(e.first, u, dist + e.second, dist_arr);
}
void dfs_final(int u, int p, int dist, int &farthest_node, int &max_dist) {
if (dist > max_dist) {
max_dist = dist;
farthest_node = u;
}
for (auto &e : merged_adj[u]) if (e.first != p) dfs_final(e.first, u, dist + e.second, farthest_node, max_dist);
}
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]});
merged_adj[A[i]].push_back({B[i], T[i]});
merged_adj[B[i]].push_back({A[i], T[i]});
}
static int dA[MAXN], dB[MAXN], dTmp[MAXN];
vector<pair<int, int>> centers;
for (int i = 0; i < N; i++) {
if (!vis[i]) {
nodes.clear();
dfs_ecc(i, -1, 0, dTmp);
int start = i;
for (int x : nodes) if (dTmp[x] > dTmp[start]) start = x;
nodes.clear();
dfs_ecc(start, -1, 0, dA);
int end = start;
for (int x : nodes) if (dA[x] > dA[end]) end = x;
nodes.clear();
dfs_ecc(end, -1, 0, dB);
int min_ecc = 2e9, best_node = i;
for (int x : nodes) {
int ecc = max(dA[x], dB[x]);
if (ecc < min_ecc) { min_ecc = ecc; best_node = x; }
}
centers.push_back({min_ecc, best_node});
}
}
// Sort centers by radius to find the absolute hub (the one with the largest radius)
sort(centers.rbegin(), centers.rend());
int hub = centers[0].second;
// Simulate Merging: Connect all other centers to the hub
for (int i = 1; i < centers.size(); i++) {
int target = centers[i].second;
merged_adj[hub].push_back({target, L});
merged_adj[target].push_back({hub, L});
}
// Final Diameter via two-pass DFS on the merged tree
int u = hub, v = hub, d1 = -1, d2 = -1;
dfs_final(hub, -1, 0, u, d1);
dfs_final(u, -1, 0, v, d2);
return d2;
}
