#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
const ll INF=2e18;
vector<pll> ed[100005];
ll dist[100005],n,m,maxx=0;
vector<ll> tmp,path;
void dfs(ll u,ll p)
{
tmp.pb(u);
for(auto v:ed[u])
{
if(v.F==p) continue;
dist[v.F]+=dist[u]+v.S;
dfs(v.F,u);
}
}
ll findpath(ll u,ll p,ll x)
{
ll ret=-1;
if(u==x) ret=dist[x];
for(auto v:ed[u])
{
if(v.F==p) continue;
ll k=findpath(v.F,u,x);
if(k!=-1) ret=dist[u];
}
path.pb(ret);
return ret;
}
ll findmid(ll st)
{
tmp.clear();
path.clear();
dfs(st,-1);
ll mx=0,s=-1;
for(ll u:tmp)
{
if(mx<dist[u]) mx=dist[u],s=u;
dist[u]=0;
}
dfs(s,-1);
mx=0;
ll t=-1;
for(ll u:tmp) if(mx<dist[u]) mx=dist[u],t=u;
maxx=max(maxx,mx);
findpath(s,-1,t);
ll mn=INF;
for(ll u:path) mn=min(mn,max(mx-u,u));
return mn;
}
int travelTime(int N,int M,int L,int A[], int B[], int T[])
{
n=N,m=M;
vector<ll> ans;
rep(i,m)
{
ll u=A[i],v=B[i],w=T[i];
ed[u].pb({v,w});
ed[v].pb({u,w});
}
rep(i,n)
{
if(dist[i]) continue;
ans.pb(findmid(i));
}
sort(ans.begin(),ans.end(),greater<ll>());
if(ans.size()==1) return maxx;
else if(ans.size()==2) return max(maxx,ans[0]+ans[1]+L);
else return max({maxx,ans[0]+ans[1]+L,ans[1]+ans[2]+2*L});
}
Compilation message
/tmp/ccvFkIZ3.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
