#include "dreaming.h"
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];
bool visited[MAXN];
vector<int> path;
int parent[MAXN], dist[MAXN];
int findFarthest(int start, int n, int &farthestNode) {
vector<int> q;
q.push_back(start);
for(int i = 0; i < n; i++) dist[i] = -1;
dist[start] = 0;
parent[start] = -1;
int head = 0;
farthestNode = start;
vector<int> component;
visited[start] = true;
component.push_back(start);
while(head < q.size()){
int u = q[head++];
if(dist[u] > dist[farthestNode]) farthestNode = u;
for(auto &edge : adj[u]){
int v = edge.first;
int w = edge.second;
if(dist[v] == -1){
dist[v] = dist[u] + w;
parent[v] = u;
visited[v] = true;
q.push_back(v);
component.push_back(v);
}
}
}
return dist[farthestNode];
}
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 max_diameter = 0;
for (int i = 0; i < N; i++) {
if (!visited[i]) {
int u, v;
findFarthest(i, N, u);
int diameter = findFarthest(u, N, v);
max_diameter = max(max_diameter, diameter);
vector<int> p;
int curr = v;
while (curr != -1) {
p.push_back(curr);
curr = parent[curr];
}
int current_radius = diameter;
int dist_from_u = 0;
for (int j = 0; j < p.size(); j++) {
current_radius = min(current_radius, max(dist_from_u, diameter - dist_from_u));
if (j + 1 < p.size()) {
for(auto &e : adj[p[j]]) {
if(e.first == p[j+1]) {
dist_from_u += e.second;
break;
}
}
}
}
radii.push_back(current_radius);
}
}
sort(radii.rbegin(), radii.rend());
int res = max_diameter;
if (radii.size() >= 2) {
res = max(res, radii[0] + radii[1] + L);
}
if (radii.size() >= 3) {
res = max(res, radii[1] + radii[2] + 2 * L);
}
return res;
}
