#include "dreaming.h"
#include <algorithm>
#include <vector>
#include <queue>
#define INF 0x7fffffff
using namespace std;
typedef pair <int,int> ppair;
vector <ppair> Road[100001];
vector <int> Diameter;
vector <int> Depth;
queue <int> Q;
int Check[100001], D[100001], Path[100001][2], Ans=-1;
int MAX(int X, int Y)
{
if(X>Y)
return X;
return Y;
}
void BFS(int S)
{
int Now, Dist, i, j, Max=-1, V, Min=INF;
Check[S]=1;
Q.push(S);
Q.push(0);
while(!Q.empty())
{
Now=Q.front();
Q.pop();
Dist=Q.front();
Q.pop();
if(Max<Dist)
{
Max=Dist;
V=Now;
}
j=Road[Now].size();
for(i=0 ; i<j ; i++)
if(!Check[Road[Now][i].first])
{
Check[Road[Now][i].first]=1;
Q.push(Road[Now][i].first);
Q.push(Dist+Road[Now][i].second);
}
}
Check[V]=2;
D[V]=0;
Path[V][0]=-1;
Max=-1;
Q.push(V);
while(!Q.empty())
{
Now=Q.front();
Q.pop();
if(Max<D[Now])
{
Max=D[Now];
V=Now;
}
j=Road[Now].size();
for(i=0 ; i<j ; i++)
if(Check[Road[Now][i].first]==1)
{
Check[Road[Now][i].first]=2;
D[Road[Now][i].first]=D[Now]+Road[Now][i].second;
Path[Road[Now][i].first][0]=Now;
Path[Road[Now][i].first][1]=Road[Now][i].second;
Q.push(Road[Now][i].first);
}
}
Diameter.push_back(Max);
Dist=0;
while(V>=0)
{
if(Min>MAX(Max,Dist))
Min=MAX(Max,Dist);
Dist+=Path[V][1];
Max-=Path[V][1];
V=Path[V][0];
}
Depth.push_back(Min);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
int i, j;
for(i=0 ; i<M ; i++)
{
Road[A[i]].push_back(make_pair(B[i],T[i]));
Road[B[i]].push_back(make_pair(A[i],T[i]));
}
for(i=0 ; i<N ; i++)
if(!Check[i])
BFS(i);
j=Diameter.size();
for(i=0 ; i<j ; i++)
{
if(Ans<Diameter[i])
Ans=Diameter[i];
}
if(j==1)
return Ans;
sort(Depth.begin(),Depth.end());
for(i=0 ; i<j-1 ; i++)
{
if(Ans<Depth[i]+Depth[j-1]+L)
Ans=Depth[i]+Depth[j-1]+L;
}
if(j==2)
return Ans;
for(i=0 ; i<j-2 ; i++)
if(Ans<Depth[i]+Depth[j-2]+2*L)
Ans=Depth[i]+Depth[j-2]+2*L;
return Ans;
}
