#include"dreaming.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
vector<pair<int,int>>nodes[100000];
bool vis[100000];
int par[100000];
int biggest_depth[100000];
int biggest_len_up[100000];
vector<int>nodes_list;
void dfs(int node){
if(vis[node])
return;
vis[node]=true;
nodes_list.push_back(node);
for(auto ne:nodes[node]){
if(vis[ne.first])
par[node]=ne.first;
else{
dfs(ne.first);
biggest_depth[node]=max(biggest_depth[node],biggest_depth[ne.first]+ne.second);
}
}
}
void dfs2(int node){
pair<int,int>deepest1,deepest2;
for(auto ne:nodes[node]){
if(ne.first==par[node])
continue;
int depth=biggest_depth[ne.first]+ne.second;
if(depth>=deepest1.first){
deepest2=deepest1;
deepest1={depth,ne.first};
}else if(depth>deepest2.first){
deepest2={depth,ne.first};
}
}
for(auto ne:nodes[node]){
if(ne.first==par[node])
continue;
if(ne.first==deepest1.second){
biggest_len_up[ne.first]=max(biggest_len_up[node],deepest2.first)+ne.second;
}else{
biggest_len_up[ne.first]=max(biggest_len_up[node],deepest1.first)+ne.second;
}
dfs2(ne.first);
}
}
pair<int,int>get_diameter(int root){
nodes_list.clear();
par[root]=-1;
dfs(root);
dfs2(root);
int res=1e9,diam=0;
for(int node:nodes_list){
diam=max(diam,biggest_depth[node]+biggest_len_up[node]);
res=min(res,max(biggest_depth[node],biggest_len_up[node]));
}
return {res,diam};
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i=0;i<M;i++){
nodes[A[i]].emplace_back(B[i],T[i]);
nodes[B[i]].emplace_back(A[i],T[i]);
}
vector<int>dists;
int diam=0;
for(int i=0;i<N;i++)
if(!vis[i]){
auto r=get_diameter(i);
dists.push_back(r.first);
diam=max(diam,r.second);
}
sort(dists.begin(),dists.end());
reverse(dists.begin(),dists.end());
if(dists.size()==1)
return max(dists[0],diam);
else if(dists.size()==2)
return max(dists[0]+dists[1]+L,diam);
else
return max(max(dists[0]+dists[1]+L,dists[1]+dists[2]+2*L),diam);
}
