#include "dreaming.h"
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
void getMaxDist(int cur, int par, vector<vector<pair<int, int> > > &adjacency, vector<int> &maxDist, vector<bool> &visited) {
visited[cur] = true;
for (auto &[nxt, len] : adjacency[cur]) {
if (nxt == par) continue;
getMaxDist(nxt, cur, adjacency, maxDist, visited);
maxDist[cur] = max(maxDist[cur], maxDist[nxt] + len);
}
}
int minDist(int cur, int par, int parMaxDist, vector<vector<pair<int, int> > > &adjacency, vector<int> &maxDist) {
vector<pair<int, pair<int, int> > > dists;
dists.push_back(make_pair(0, make_pair(-1, -1)));
for (auto &[nxt, len] : adjacency[cur]) {
if (nxt == par) dists.push_back(make_pair(parMaxDist, make_pair(par, len)));
else dists.push_back(make_pair(maxDist[nxt] + len, make_pair(nxt, len)));
}
sort(dists.rbegin(), dists.rend());
if (dists.size() == 1) return 0;
if (dists[1].first + dists[0].second.second < dists[0].first) {
return minDist(dists[0].second.first, cur, dists[1].first + dists[0].second.second, adjacency, maxDist);
}
return dists[0].first;
}
int maxDistWithIn(int cur, int par, vector<vector<pair<int, int> > > &adjacency, vector<int> &maxDist) {
vector<int> dists(2, 0);
int maxRes = 0;
for (auto &[nxt, len] : adjacency[cur]) {
if (nxt == par) continue;
maxRes = max(maxRes, maxDistWithIn(nxt, cur, adjacency, maxDist));
dists.push_back(maxDist[nxt] + len);
}
sort(dists.rbegin(), dists.rend());
return max(maxRes, dists[0] + dists[1]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<int, int> > > adjacency(N);
for (int i = 0; i < M; ++i) {
adjacency[A[i]].emplace_back(B[i], T[i]);
adjacency[B[i]].emplace_back(A[i], T[i]);
}
vector<int> maxDist(N);
vector<int> components;
vector<bool> visited(N, false);
int maxRes = 0;
for (int i = 0; i < N; ++i) {
if (visited[i]) continue;
getMaxDist(i, -1, adjacency, maxDist, visited);
components.push_back(minDist(i, -1, -1, adjacency, maxDist));
maxRes = max(maxRes, maxDistWithIn(i, -1, adjacency, maxDist));
}
sort(components.rbegin(), components.rend());
if (components.size() == 1) return max(components[0], maxRes);
else if (components.size() == 2) return max(components[0] + components[1] + L, maxRes);
else return max(components[1] + max(components[0] + L, components[2] + 2 * L), maxRes);
}
