#include <algorithm>
#include <iostream>
#include <vector>
#include "dreaming.h"
void calculateDepths(const std::vector<std::vector<std::pair<int, int>>> &adj,
std::vector<int> &component, std::vector<int> &depths,
int node, int parent) {
component.push_back(node);
int depth = 0;
for (auto [n, l] : adj[node]) {
if (n == parent) continue;
calculateDepths(adj, component, depths, n, node);
depth = std::max(depth, l + depths[n]);
}
depths[node] = depth;
}
void calculateEccentricities(
const std::vector<std::vector<std::pair<int, int>>> &adj,
std::vector<int> &depths, std::vector<int> &eccentricities, int &diameter,
int up, int node, int parent) {
int down = up;
int second_down = 0;
int c = 0;
for (auto [n, l] : adj[node]) {
if (n == parent) continue;
c += 1;
int q = l + depths[n];
if (q > down) {
second_down = down;
down = q;
} else if (q > second_down) {
second_down = q;
}
}
eccentricities[node] = down;
diameter = std::max(diameter, down + second_down);
std::vector<int> suffixes(adj[node].size() + 1);
suffixes.push_back(0);
for (int i = adj[node].size() - 1; i > 0; i--) {
auto [n, l] = adj[node][i];
if (n == parent)
suffixes.push_back(std::max(suffixes.back(), up));
else
suffixes.push_back(std::max(suffixes.back(), l + depths[n]));
}
std::reverse(suffixes.begin(), suffixes.end());
int prefix = 0;
for (int i = 0; i < adj[node].size(); i++) {
auto [n, l] = adj[node][i];
if (n == parent) {
prefix = std::max(prefix, up);
} else {
calculateEccentricities(adj, depths, eccentricities, diameter,
std::max(prefix, suffixes[i]) + l, n, node);
prefix = std::max(prefix, l + depths[n]);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
std::vector<std::vector<std::pair<int, int>>> adj(N);
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]});
}
std::vector<bool> visited(N, false);
std::vector<int> depths(N), eccentricities(N);
std::vector<int> component;
std::vector<int> q;
int internal_worst = 0;
for (int i = 0; i < N; i++) {
if (!visited[i]) {
component.clear();
calculateDepths(adj, component, depths, i, -1);
int diameter = 0;
calculateEccentricities(adj, depths, eccentricities, diameter, 0, i,
-1);
internal_worst = std::max(internal_worst, diameter);
int centre = i;
int eccentricity = eccentricities[i];
for (int n : component) {
visited[n] = true;
if (eccentricities[n] < eccentricity) {
eccentricity = eccentricities[n];
centre = n;
}
}
q.push_back(eccentricity);
}
}
std::sort(q.begin(), q.end(), std::greater<int>{});
if (q.size() == 1) {
return internal_worst;
} else if (q.size() == 2) {
return std::max(internal_worst, q[0] + q[1] + L);
} else {
return std::max(internal_worst,
std::max(q[0] + q[1] + L, q[1] + q[2] + 2 * L));
}
}
