#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iostream>
#include <cassert>
#include <bitset>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
#pragma optimize("O3")
using namespace std;
// template<typename T>
// using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
// template<typename T, typename S>
// using ordered_map = __gnu_pbds::tree<T, S, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template<typename T, typename S>
ostream& operator<< (ostream& out, pair<T, S> p) {
return out << "(" << p.first << ", " << p.second << ")";
}
// any ct except std::string
template<typename Container,
typename S = typename enable_if<!is_same<Container, string>::value, typename Container::value_type>::type>
ostream& operator<<(ostream& __out, Container &__ct) {
__out << "{";
bool first = true;
for(auto&& __el : __ct) {
if(!first) __out << ", ";
__out << __el;
first = false;
}
return __out << "}";
}
// bitset
template<size_t N>
ostream& operator<<(ostream& __out, bitset<N> &__bs) {
__out << "{";
for(size_t i = 0; i < N; ++i) __out << (i != 0 ? ", " : "") /*<< boolalpha*/ << __bs[N - i - 1];
return __out << "}";
}
template<typename Tail>
void _dbg(Tail T) {
cerr << T << '\n';
}
template<typename Head, typename... Tail>
void _dbg(Head H, Tail... T) {
cerr << H << ", ";
_dbg(T...);
}
#ifdef DEBUG
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: "; _dbg(__VA_ARGS__);
#else
#define dbg(...) 42
#endif
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vii> AL(N, vii());
for(int i = 0; i < M; ++i) {
AL[A[i]].emplace_back(B[i], T[i]);
AL[B[i]].emplace_back(A[i], T[i]);
}
vi sizes;
sizes.reserve(N);
vi diametri;
diametri.reserve(N);
vi dist_fw(N, -1);
vi dist_bw(N, -1);
// calcola le distanze dei cc
for(int start = 0; start < N; ++start) {
// non visitato
if(dist_fw[start] == -1) {
// calcola longest path, ricalcolala, prova tutti i nodi in mezzo alla strada piu' lunga
// parti da u
queue<int> q;
dist_fw[start] = 0;
q.emplace(start);
int furthest = start;
int furthest_dist = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
for(auto &[v, w] : AL[u]) {
if(dist_fw[v] == -1) {
dist_fw[v] = dist_fw[u] + w; // una sola strada possibile
q.emplace(v);
if(dist_fw[v] > furthest_dist) {
furthest = v;
furthest_dist = dist_fw[v];
}
}
}
}
// rigira la bfs partendo dal piu' distante
dist_bw.clear();
dist_bw[furthest] = 0;
q.emplace(furthest);
int end = furthest;
int end_dist = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
for(auto &[v, w] : AL[u]) {
if(dist_bw[v] == -1) {
dist_bw[v] = dist_bw[u] + w; // una sola strada possibile
q.emplace(v);
if(dist_bw[v] > end_dist) {
end = v;
end_dist = dist_bw[v];
}
}
}
}
dbg(furthest, end); // diametro
int to = end;
// percorri tutti i nodi tra start ed end, trova il migliore
int best = dist_bw[to];
while(furthest != to) {
// avvicinati ad end
dbg(to);
int next = AL[to][0].first;
int next_dist = dist_bw[next];
for(auto &[v, w] : AL[to]) {
if(dist_bw[v] < next_dist) {
next = v;
next_dist = dist_bw[v];
}
}
to = next;
best = min(best, max(dist_bw[to], dist_bw[end] - dist_bw[to]));
}
diametri.push_back(dist_bw[end]);
sizes.push_back(best);
}
}
dbg(diametri, sizes);
if(sizes.size() == 1) {
return diametri[0];
}
else {
nth_element(sizes.begin(), sizes.end()-1-0, sizes.end());
int first = *(sizes.end()-1-0);
nth_element(sizes.begin(), sizes.end()-1-1, sizes.end());
int second = *(sizes.end()-1-1);
int ans = max(
*max_element(diametri.begin(), diametri.end()),
first + L + second
);
if(sizes.size() == 2) return ans;
nth_element(sizes.begin(), sizes.end()-1-2, sizes.end());
int third = *(sizes.end()-1-2);
return max(ans, second + third + 2 * L);
}
}
