#include "dreaming.h"
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100100;
int longest[MAXN];
int longestChild[MAXN];
int secondLongest[MAXN];
int secondLongestChild[MAXN];
bool visited[MAXN];
vector<pair<int,int>> ADJ[MAXN];
int dfs(int node, int parent) {
visited[node] = true;
for (auto [child, w] : ADJ[node]) {
if (child == parent) continue;
int ln = dfs(child, node) + w;
if (ln > secondLongest[node]) {
secondLongest[node] = ln;
secondLongestChild[node] = child;
if (secondLongest[node] > longest[node]) {
swap(secondLongest[node], longest[node]);
swap(secondLongestChild[node], longestChild[node]);
}
}
}
return longest[node];
}
int min_max_dfs(int node, int parent, int other) {
if (ADJ[node].size() == 0) return 0;
int best = 2000000000;
for (auto [child, w] : ADJ[node]) {
if (child == parent) continue;
if (child != longestChild[node]) {
best = min(best, min_max_dfs(child, node, max(other,longest[node]) + w));
} else {
best = min(best, min_max_dfs(child, node, max(other, secondLongest[node]) + w));
}
}
// cout << "\n" << node << " " << other << " " << longest[node] << "\n\n";
return min(best, max(other,longest[node]));
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
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]);
}
for (int i = 0; i < N; i++) {
longestChild[i] = -1;
}
priority_queue<int> pq;
pq.push(0);
pq.push(0);
for (int i = 0; i < N; i++) {
if (visited[i]) continue;
dfs(i, i);
int num = min_max_dfs(i,i,0);
pq.push(num);
// cout << i << " " << num << "\n";
// cout << longest[i] << " " << secondLongest[i] << "\n";
}
if (M == N-1) {
return pq.top();
}
int a = pq.top();
pq.pop();
int b = pq.top();
pq.pop();
return a+b+L;
}
