#include "dreaming.h"
#include<queue>
#include<vector>
#include<iostream>
using namespace std;
///Diameter of a tree
///Determine the minimum longest path selecting optimal connections
struct edge
{
int from,to;
int w;
};
int color[100005];
int d[2][100005]; //Distance from node 1 and node 2
queue<int> Q;
vector<edge> adjList[100005];
int bfs(int s,int node,int c) ///Returns the farest node of s
{
color[s]=c;
d[node][s]=0;
Q.push(s);
int maximum=0;
int max_Node=s;
while(Q.size()){
int u=Q.front();Q.pop();
for(edge e: adjList[u]){
int v=e.to;
if(color[v]!=c){
color[v]=c;
d[node][v]=d[node][u]+e.w;
if(d[node][v]>maximum){
maximum=d[node][v];
max_Node=v;
}
Q.push(v);
}
}
}
return max_Node;
}
int getMinimum_FarestDistance(int s,int c) ///Returns the minimum longest distance in a tree
{
color[s]=c;
Q.push(s);
int minimum=1000000000;
while(Q.size()){
int u=Q.front();Q.pop();
if(max(d[0][u],d[1][u]) < minimum){
minimum=max(d[0][u],d[1][u]);
}
for(edge e: adjList[u]){
int v=e.to;
if(color[v]!=c){
color[v]=c;
Q.push(v);
}
}
}
return minimum;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<M;i++){
edge e={A[i],B[i],T[i]};
adjList[ A[i] ].push_back(e);
swap(e.from,e.to);
adjList[ B[i] ].push_back(e);
}
int c=1;
int best[5];
int j=0;
int answer=0;
for(int i=0;i<N;i++){
if(color[i]!=0) continue;
int u=bfs(i,0,c++); //Gets the farest node of i
int v=bfs(u,1,c++); //Gets the farest node of u
//u and v are the farest nodes between themselves in the tree
answer=max(answer,d[1][v]);
bfs(v,0,c++);
best[j++]=getMinimum_FarestDistance(i,c);
}
int NewPath=best[0]+best[1]+L;
answer=max(answer,NewPath);
return answer;
}
