#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<bool> vis, comp;
vector<int> diapath, diaedges;
vector<int> parent;
pair<ll, ll> get_furthest(int node, int N){
vis.assign(N, false);
queue<pair<int, int>> q;
vector<pair<int, int>> nodes;
ll dist = 0, ret = node;
q.push({node, 0});
while(!q.empty()){
pair<int, int> val = q.front();
nodes.push_back(val);
vis[val.first] = true;
comp[val.first] = true;
q.pop();
if(val.second > dist){
ret = val.first;
dist = val.second;
}
for(pair<int, int> i : adj[val.first]){
if(!vis[i.first]){
parent[i.first] = val.first;
q.push({i.first, i.second + val.second});
}
}
}
return {ret, dist};
}
ll diameter(int node, int N){
diapath.clear(), diaedges.clear();
int a, b, p;
pair<int, int> dia;
a = get_furthest(node, N).first;
dia = get_furthest(a, N);
b = dia.first;
p = b;
while(p != a){
diapath.push_back(p);
for(pair<int, int> i : adj[p]) if(i.first == parent[p]) diaedges.push_back(i.second);
p = parent[p];
}
diapath.push_back(a);
return dia.second;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N), parent.resize(N), comp.resize(N);
int bigcenter = -1, maxrad = -1;
vector<int> centers;
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]});
}
for(int i = 0; i < N; i++){
if(!comp[i]){
ll dialength = max(diameter(i, N), 0ll);
ll c = i, p = 0, mindist = dialength;
if(dialength > 0){
for(int j = 0; j < diapath.size(); j++){
if(max(p, dialength - p) < mindist){
c = diapath[j];
mindist = max(p, dialength - p);
}
if(j < diaedges.size()) p += diaedges[j];
}
}
if(mindist > maxrad){
bigcenter = c;
maxrad = mindist;
}
// cerr << endl << "center at " << c << endl;
centers.push_back(c);
}
}
for(int i : centers){
if(i != bigcenter){
// cerr << i << ' ';
adj[i].push_back({bigcenter, L});
adj[bigcenter].push_back({i, L});
}
}
// cerr << endl;
ll ret = diameter(0, N);
return ret;
}
