#include "dreaming.h"
#include <vector>
#include <algorithm>
using namespace std;
pair<int, int> furthest(int v, int p, vector<bool> &used, vector<vector<pair<int, int>>> &adj)
{
used[v] = true;
pair<int, int> res = {v, 0};
for (auto [u, w] : adj[v])
{
if (u == p) continue;
pair<int, int> ret = furthest(u, v, used, adj);
ret.second += w;
if (ret.second > res.second) res = ret;
}
return res;
}
bool findPath(int v, int p, int e, vector<vector<pair<int, int>>> &adj, vector<int> &path)
{
if (v == e) return true;
for (auto [u, w] : adj[v])
{
if (u == p) continue;
bool ret = findPath(u, v, e, adj, path);
if (ret)
{
path.push_back(w);
return true;
}
}
return false;
}
void dfs(int v, int p, vector<vector<pair<int, int>>> &adj, vector<int> &vertices, vector<bool> &used)
{
used[v] = true;
vertices.push_back(v);
for (auto [u, w] : adj[v]) if (u != p) dfs(u, v, adj, vertices, used);
}
int dfs2(int v, int p, vector<vector<pair<int, int>>> &adj)
{
int maxd = 0;
for (auto [u, w] : adj[v])
{
if (u == p) continue;
int d = dfs2(u, v, adj);
maxd = max(maxd, d + w);
}
return maxd;
}
int travelTime(int n, int m, int l, int A[], int B[], int T[])
{
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < m; ++i)
{
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
vector<bool> used(n);
vector<int> weights;
for (int i = 0; i < n; ++i)
{
if (!used[i])
{
vector<int> vertices;
dfs(i, -1, adj, vertices, used);
int minD = 1e9;
for (int j : vertices) minD = min(minD, dfs2(j, -1, adj));
weights.push_back(minD);
/*int a = furthest(i, -1, used, adj).first;
int b = furthest(a, -1, used, adj).first;
if (a == b)
{
weights.push_back(0);
continue;
}
vector<int> path;
findPath(a, -1, b, adj, path);
int minRes = 1e9 + 1, suff = 0, pref = 0;
for (int j = (int)path.size() - 1; j >= 0; --j) suff += path[j];
for (int j = 0; j < path.size(); ++j)
{
minRes = min(minRes, max(suff, pref));
pref += path[j];
suff -= path[j];
}
weights.push_back(minRes);*/
}
}
sort(weights.begin(), weights.end(), greater<>());
if (weights.size() == 1) return weights[0];
if (weights.size() == 2) return weights[0] + weights[1] + l;
return max(weights[0] + weights[1] + l, weights[1] + weights[2] + 2 * l);
}
