#include "grader.h"
#include <bits/stdc++.h>
#define F first
#define S second
typedef long long ll;
using namespace std;
int n,m,l;
int ans=0;
vector<pair<int,int> > v[100010];
vector<int> comp;
vector<int> cent;
int cc[100010];
pair<int,int> dep[100010];
int par[100010];
void dfscc(int nod,int pt,int c){
par[nod]=pt;
cc[nod]=c;
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==pt)continue;
dfscc(v[nod][i].F,nod,c);
}
}
pair<int,int> dfsdia (int nod,int pt){
pair<int,int> res={0,nod};
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==pt)continue;
pair<int,int> x=dfsdia(v[nod][i].F,nod);
res=max(res,{x.F+v[nod][i].S,x.S});
}
return res;
}
int dia(int nod0){
return dfsdia(dfsdia(nod0,-1).S,-1).F;
}
pair<int,int> dfsdep (int nod,int pt){
pair<int,int> res={0,nod};
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==pt)continue;
pair<int,int> x=dfsdep(v[nod][i].F,nod);
res=max(res,{x.F+v[nod][i].S,v[nod][i].F});
}
dep[nod]=res;
return res;
}
int center (int nod0){
dfsdep(nod0,-1);
if (v[nod0].size()==0){
return 0;
}
int mx=0;
int nod=nod0;
while (1){
int nxt=dep[nod].S;
int edge=0;
int mx1=0;
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==nxt){
edge=v[nod][i].S;
break;
}
}
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==nxt||v[nod][i].F==par[nod])continue;
mx1=max(mx1,dep[v[nod][i].F].F+v[nod][i].S);
//cout <<mx<<endl;
}
mx1=max(mx,mx1);
/*cout <<mx<<endl;
cout <<dep[nod].F<<" = "<<dep[nod].S<<endl;
cout <<dep[nxt].F<<" = "<<dep[nxt].S<<endl;
cout <<nod<<" -- "<<nxt<<endl;
cout <<mx<<" "<<mx1<<endl;
// break;*/
if (dep[nxt].F<=mx1+edge){
/* cout <<dep[nod].F<<" = "<<dep[nod].S<<endl;
cout <<dep[nxt].F<<" = "<<dep[nxt].S<<endl;
cout <<nod<<" -- "<<nxt<<endl;
cout <<mx<<" "<<mx1<<endl;*/
return min( max(dep[nod].F,mx) , max(mx1+edge,dep[nxt].F) );
}else {
nod=nxt;
mx=mx1+edge;
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
memset(cc,-1,sizeof cc);
n=N;m=M;l=L;
for (int i=0;i<m;i++){
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
for (int i=0;i<n;i++){
if (cc[i]==-1){
comp.push_back(i);
dfscc(i,-1,i);
}
}
for (int i=0;i<comp.size();i++){
ans=max(ans,dia(comp[i]));
//cout <<"---------------\n";
cent.push_back(center(comp[i]));
//cout <<cent[i]<<" "<<i<<endl;
}
//cout <<endl;
sort(cent.begin(),cent.end());
reverse(cent.begin(),cent.end());
if (cent.size()<=1){
return ans;
}else {
ans=max(ans,cent[0]+cent[1]+l);
if (cent.size()>=3){
ans=max(ans,cent[1]+cent[2]+l+l);
}
}
return ans;
}
/*
int main (){
int n,m,l;
int a[100010];
int b[100010];
int t[100010];
cin >>n>>m>>l;
for (int i=0;i<m;i++){
cin >>a[i]>>b[i]>>t[i];
}
cout <<travelTime(n,m,l,a,b,t)<<endl;
return 0;
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
Compilation message
dreaming.cpp:1:10: fatal error: grader.h: No such file or directory
#include "grader.h"
^~~~~~~~~~
compilation terminated.
