#include <bits/stdc++.h>
#include "dreaming.h"
#define MAX 105000
typedef std::pair<int,int> pii;
std::vector<pii> con[MAX];
bool foi[MAX];
int visitou[MAX]={};
int turno=42;
int mais_distante(int x){
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,x});
int last=0;
++turno;
while(queue.size()){
auto __ = queue.top();
queue.pop();
if(visitou[__.second]==turno)continue;
visitou[__.second]=turno;
last=__.second;
for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
}
return last;
}
int maior_distancia(int x){
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,x});
int last=0;
++turno;
while(queue.size()){
auto __ = queue.top();
queue.pop();
if(visitou[__.second]==turno)continue;
visitou[__.second]=turno;
last=__.first;
for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
}
return last;
}
std::vector<int> marcar(int x){
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,x});
std::vector<int> v;
++turno;
while(queue.size()){
auto __ = queue.top();
queue.pop();
if(visitou[__.second]==turno)continue;
visitou[__.second]=turno;
v.push_back(__.second);
foi[__.second]=true;
for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
}
return v;
}
int maiordist[MAX]={};
int meio(int x){
int ponta1 = mais_distante(mais_distante(x));
int ponta2 = mais_distante(ponta1);
std::vector<int> checar;
{
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,ponta1});
++turno;
while(queue.size()){
auto __ = queue.top();
queue.pop();
if(visitou[__.second]==turno)continue;
visitou[__.second]=turno;
checar.push_back(__.second);
maiordist[__.second]=__.first;
for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
}
}
{
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
queue.push({0,ponta2});
++turno;
while(queue.size()){
auto __ = queue.top();
queue.pop();
if(visitou[__.second]==turno)continue;
visitou[__.second]=turno;
maiordist[__.second]=std::max(maiordist[__.second],__.first);
for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
}
}
int best=-1;
int val=1e9+7;
for(auto&x:checar){
if(maiordist[x]<val){
val=maiordist[x];
best=x;
}
}
return best;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i=0;i!=M;++i){
con[A[i]].push_back({B[i],T[i]});
con[B[i]].push_back({A[i],T[i]});
}
std::vector<std::vector<int>> vec;
for(int i=0;i!=N;++i){
if(foi[i])continue;
vec.push_back(marcar(i));
}
std::vector<pii> meios;
for(auto&x:vec){
int k = meio(x[0]);
meios.push_back({maior_distancia(k),meio(x[0])});
}
std::sort(meios.begin(),meios.end(),std::greater<pii>());
for(int i=1;i<meios.size();++i){
con[meios[i].second].push_back({meios[0].second,L});
con[meios[0].second].push_back({meios[i].second,L});
}
return maior_distancia(mais_distante(mais_distante(0)));
}
