#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <vector>
#include "dreaming.h"
constexpr int INF = INT_MAX / 2;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
std::vector<std::vector<std::pair<int, int>>> G(N);
for (int i{}; i < M; ++i) {
G[A[i]].emplace_back(B[i], T[i]);
G[B[i]].emplace_back(A[i], T[i]);
}
std::vector<int> D(N, INF);
std::function<int(int)> dfs = [&](int i) {
auto &d = D[i] = 0;
for (auto &[u, w] : G[i])
if (D[u] == INF) d = std::max(d, dfs(u) + w);
return d;
};
auto const wc = [&](int i) {
int R = dfs(i);
for (;;) {
int c = N;
int p = 0;
int q = 0;
D[i] = 0;
for (auto [u, w] : G[i]) {
auto d = w + D[u];
if (d >= p) {
std::swap(u, c);
std::swap(d, p);
std::swap(w, q);
}
D[i] = std::max(D[i], d);
}
if (c == N) return R;
D[c] = std::max(D[c], D[i] + q);
i = c;
if (D[i] >= R) return R;
R = D[i];
}
};
auto const diam = [&](int start) {
std::vector<int> Q{start};
D[start] = 0;
for (size_t i{}; i < Q.size(); ++i) {
auto v = Q[i];
for (auto [u, w] : G[v])
if (D[v] + w < D[u]) {
D[u] = D[v] + w;
Q.push_back(u);
}
}
auto m = *max_element(Q.begin(), Q.end(), [&](auto a, auto b) { return D[a] < D[b]; });
for (auto q : Q) D[q] = INF;
Q.push_back(m);
D[m] = 0;
for (size_t i{}; i < Q.size(); ++i) {
auto v = Q[i];
for (auto [u, w] : G[v])
if (D[v] + w < D[u]) {
D[u] = D[v] + w;
Q.push_back(u);
}
}
m = *max_element(Q.begin(), Q.end(), [&](auto a, auto b) { return D[a] < D[b]; });
return D[m];
};
std::vector<int> C;
for (int i{}; i < N; ++i)
if (D[i] == INF) C.push_back(wc(i));
sort(C.begin(), C.end(), std::greater{});
int R{};
if (C.size() >= 2) R = std::max(R, C[0] + C[1] + L);
if (C.size() >= 3) R = std::max(R, C[1] + C[2] + L + L);
D.assign(N, INF);
for (int i{}; i < N; ++i)
if (D[i] == INF) R = std::max(R, diam(i));
return R;
}
