#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include "dreaming.h"
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,mod=1000000007,lg=20,root=1000,inf=1e18;
int pa[mxn+10],mxdist[mxn+10],dist[mxn+10],mn[mxn+10];
vector<pii>adj[mxn+10];
vector<int>g[mxn+10];
bitset<mxn+10>yes,u;
int find(int u){return (u==pa[u])?u:pa[u]=find(pa[u]);}
void merg(int u,int v){
int a=find(u),b=find(v);
pa[a]=b;
}
void dfs(int cur,int p){
for(auto i:adj[cur]){
if(i.f==p)continue;
dist[i.f]=dist[cur]+i.s;
dfs(i.f,cur);
}
}
void solve(int st){
pii cur={st,0};
while(cur.f!=-1){
for(auto i:g[st])dist[i]=0;
dfs(cur.f,-1);
u[cur.f]=true;
cur.f=-1;
for(auto i:g[st]){
if(mxdist[i]>=dist[i])continue;
mxdist[i]=dist[i];
if(cur.f==-1&&!u[i])cur={i,dist[i]};
else if(dist[i]>cur.s&&!u[i])cur={i,dist[i]};
}
}
for(auto i:g[st])mn[st]=min(mn[st],mxdist[i]);
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i=0;i<N;i++)pa[i]=i;
for(int i=0;i<M;i++){
adj[A[i]].pb({B[i],T[i]});
adj[B[i]].pb({A[i],T[i]});
merg(A[i],B[i]);
}
for(int i=0;i<N;i++)g[find(i)].pb(i);
vector<int>head;
fill(mn,mn+N+1,INT_MAX);
int ans=0;
for(int i=0;i<N;i++){
if(yes[pa[i]])continue;
solve(pa[i]);
yes[pa[i]]=true;
head.pb(mn[pa[i]]);
}
for(int i=0;i<N;i++)ans=max(ans,mxdist[i]);
sort(rall(head));
if(head.size()>=1)ans=max(ans,head[0]);
if(head.size()>=2)ans=max(ans,head[0]+head[1]+L);
if(head.size()>=3)ans=max(ans,head[1]+head[2]+(2*L));
return ans;
}
/*
int32_t main(){
fastio
int n,m;cin>>n>>m;
int a[m],b[m],t[m];
for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>t[i];
cout<<travelTime(n,m,2,a,b,t);
}*/
Compilation message
/usr/bin/ld: /tmp/ccquwMVc.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
