#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector< vector< pair< int , int > > > adj;
vector< int > color;
vector< int > max_distance;
vector< pair< int , int > > minPossibleMaxDistance;
int color_counter;
void DFSAndcolor(int node,int parent){
color[node] = color_counter;
for(int i = 0 ;i < (int)adj[node].size();i++){
if(adj[node][i].first != parent)
DFSAndcolor(adj[node][i].first , node);
}
}
bool DFS(int node,int parent,int destination){
if(node == destination)
return true;
for(int i = 0 ;i < (int)adj[node].size();i++){
if(adj[node][i].first == parent)
continue;
if(DFS(adj[node][i].first, node, destination))
return true;
}
return false;
}
int maximum_distance , best_node;
void DFS2(int node,int parent,int distance){
if(distance > maximum_distance){
maximum_distance = distance;
best_node = node;
}
for(int i = 0 ;i < (int)adj[node].size();i++){
if(adj[node][i].first != parent)
DFS2(adj[node][i].first , node , distance + adj[node][i].second);
}
}
void DFS3(int node,int parent,int distance){
max_distance[node] = max(max_distance[node] , distance);
for(int i = 0 ;i < (int)adj[node].size();i++){
if(adj[node][i].first != parent)
DFS3(adj[node][i].first, node, distance + adj[node][i].second);
}
}
int FindLongestPath(){
maximum_distance = -1;
DFS2(0 , -1 , 0);
maximum_distance = -1;
DFS2(best_node , -1 , 0);
return maximum_distance;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N);
color.resize(N , -1);
max_distance.resize(N , -1);
for(int i = 0 ;i < M;i++){
adj[A[i]].push_back(make_pair(B[i] , T[i]));
adj[B[i]].push_back(make_pair(A[i] , T[i]));
}
for(int i = 0 ;i < N;i++){
if(color[i] != -1)
continue;
DFSAndcolor(i , -1);
color_counter++;
maximum_distance = -1;
DFS2(i , -1 , 0);
int x = best_node;
maximum_distance = -1;
DFS2(x , -1 , 0);
int y = best_node;
DFS3(x , -1 , 0);
DFS3(y , -1 , 0);
}
minPossibleMaxDistance.resize(color_counter , make_pair((int)1e9 , -1));
for(int i = 0 ;i < N;i++){
if(max_distance[i] < minPossibleMaxDistance[color[i]].first)
minPossibleMaxDistance[color[i]] = make_pair(max_distance[i] , i);
//node i is at the component with color, color[i] , has max distance with value of maximum_distance[i]
}
sort(minPossibleMaxDistance.begin(), minPossibleMaxDistance.end());
for(int i = 0 ;i < (int)minPossibleMaxDistance.size() - 1;i++){
int current_best_node = minPossibleMaxDistance[i].second;
int node_in_the_middle = minPossibleMaxDistance.back().second;
adj[current_best_node].push_back(make_pair(node_in_the_middle , L));
adj[node_in_the_middle].push_back(make_pair(current_best_node , L));
}
return FindLongestPath();
}
