#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<pair<ll, ll> > > adjList;
vector<bool> visited;
vector<bool> visitedDiameter;
pair<ll, ll> dfs1(ll u) {
queue<pair<ll, ll> > q;
q.push({u, 0LL});
ll maxDist = 0, maxDistNode = u;
while (!q.empty()) {
auto &[currNode, currDist] = q.front();
q.pop();
visited[currNode] = true;
visitedDiameter[currNode] = true;
if (maxDist < currDist) {
maxDist = currDist, maxDistNode = currNode;
}
for (auto &[v, w]: adjList[currNode]) {
if (visitedDiameter[v]) continue;
q.push({v, w + currDist});
}
}
return {maxDist, maxDistNode};
}
bool foundPath = false;
vector<ll> thePathFound;
void getCompletePath(ll u, ll finish, vector<ll> &path) {
visitedDiameter[u] = true;
if (foundPath) return;
if (u == finish) {
thePathFound = path;
foundPath = true;
return;
}
for (auto &[v, w]: adjList[u]) {
if (visitedDiameter[v]) continue;
path.push_back(v);
getCompletePath(v, finish, path);
path.pop_back();
}
}
map<pair<ll, ll>, ll> edgeWeights;
pair<ll, ll> getCR(ll startingNode) {
ll N = adjList.size();
visitedDiameter.clear();
visitedDiameter.resize(N, false);
ll farthestNode = dfs1(startingNode).second;
visitedDiameter.clear();
visitedDiameter.resize(N, false);
auto [distFromOtherEnd, otherEndOfDiameter] = dfs1(farthestNode);
foundPath = false;
visitedDiameter.clear();
visitedDiameter.resize(N, false);
vector<ll> p;
p.push_back(farthestNode);
getCompletePath(farthestNode, otherEndOfDiameter, p);
// cout << "path: ";
// for (auto l: thePathFound) {
// cout << l << ", ";
// }
// cout << " (" << distFromOtherEnd << ")" << endl;
ll bestCenterDist = distFromOtherEnd, bestCenter = farthestNode;
ll oneEnd = 0, otherEnd = distFromOtherEnd;
for (ll i = 0; i < thePathFound.size() - 1; i++) {
ll currEdgeWeight = edgeWeights[make_pair(min(thePathFound[i], thePathFound[i + 1]), max(thePathFound[i], thePathFound[i + 1]))];
oneEnd += currEdgeWeight;
otherEnd -= currEdgeWeight;
if (bestCenterDist > max(oneEnd, otherEnd)) {
bestCenterDist = max(oneEnd, otherEnd);
bestCenter = thePathFound[i + 1];
}
}
return {bestCenter, bestCenterDist};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adjList.clear();
adjList.resize(N);
visited.clear();
visited.resize(N, false);
for (ll i = 0; i < M; i++) {
adjList[A[i]].push_back({B[i], T[i]});
adjList[B[i]].push_back({A[i], T[i]});
edgeWeights[make_pair(min(A[i], B[i]), max(A[i], B[i]))] = T[i];
}
// Find all the centers and radii of the islands
vector<pair<ll, ll> > centerAndRadius;
for (ll i = 0; i < N; i++) {
if (!visited[i]) {
auto [currCenter, currRadius] = getCR(i);
centerAndRadius.push_back({currRadius, currCenter});
}
}
// connect all of them as a star graph
sort(centerAndRadius.begin(), centerAndRadius.end());
for (ll i = 0; i < centerAndRadius.size() - 1; i++) {
adjList[centerAndRadius[i].second].push_back({centerAndRadius[centerAndRadius.size() - 1].second, L});
adjList[centerAndRadius[centerAndRadius.size() - 1].second].push_back({centerAndRadius[i].second, L});
}
// get longest path again
visitedDiameter.clear();
visitedDiameter.resize(N, false);
ll farthestNode = dfs1(0).second;
visitedDiameter.clear();
visitedDiameter.resize(N, false);
auto [distFromOtherEnd, otherEndOfDiameter] = dfs1(farthestNode);
return distFromOtherEnd;
}
// const ll MAX_N = 1e5;
// static int A[MAX_N];
// static int B[MAX_N];
// static int T[MAX_N];
// int main() {
// int N, M, L, i;
// cin >> N >> M >> L;
// for (i = 0; i < M; i++)
// cin >> A[i] >> B[i] >> T[i];
// int answer = travelTime(N, M, L, A, B, T);
// printf("%d\n", answer);
// return 0;
// }
