#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector< vector< pair< int , int > > > adj;
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);
}
}
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);
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]));
}
int ans = (int)1e9;
for(int i = 0 ;i < N;i++){
for(int j = i + 1;j < N;j++){
if(DFS(i , -1 , j))
continue;
adj[i].push_back(make_pair(j , L));
adj[j].push_back(make_pair(i , L));
//cout << i << " " << j << " " << L << " : " << FindLongestPath() << endl;
ans = min(ans , FindLongestPath());
adj[i].pop_back();
adj[j].pop_back();
}
}
return ans;
}
