#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define chmin(a,b) a=(a<b?a:b)
#define chmax(a,b) a=(a>b?a:b)
const int mxn=1e5+5;
vector<pair<int,int>>adj[mxn];
pair<int,int>dp[mxn];
bool vis[mxn];
int dp2[mxn];
void dfs(int v,int pa){
vis[v]=1;
for(auto [u,len]:adj[v]){
if(u==pa)
continue;
dfs(u,v);
if(dp[v].F<=dp[u].F+len){
dp[v].S=dp[v].F;
dp[v].F=dp[u].F+len;
}
else if(dp[v].S<dp[u].F+len){
dp[v].S=dp[u].F+len;
}
}
}
pair<int,int> mn;
int mx=-2e9;
void reroot(int v,int pa){
chmin(mn,make_pair(dp[v].F,v));
for(auto [u,len]:adj[v]){
if(u==pa)
continue;
int x;
if(dp[v].F!=dp[u].F+len){
x=dp[v].F;
}
else{
x=dp[v].S;
}
x+=len;
if(dp[u].F<=x){
dp[u].S=dp[u].F;
dp[u].F=x;
}
else if(dp[u].S<x){
dp[u].S=x;
}
reroot(u,v);
}
}
void dfs2(int v,int pa){
for(auto [u,len]:adj[v]){
if(u==pa)
continue;
dfs2(u,v);
chmax(mx,dp2[v]+dp2[u]+len);
chmax(dp2[v],dp2[u]+len);
}
}
vector<pair<int,int>>v;
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
for(int i=0;i<m;i++){
adj[a[i]].push_back({b[i],t[i]});
adj[b[i]].push_back({a[i],t[i]});
}
for(int i=1;i<=n;i++){
if(vis[i])
continue;
mn={2e9,2e9};
dfs(i,i);
reroot(i,i);
v.push_back(mn);
}
sort(v.begin(),v.end(),greater<pair<int,int>>());
for(int i=1;i<(int)v.size();i++){
adj[v[0].S].push_back({v[i].S,l});
adj[v[i].S].push_back({v[0].S,l});
}
dfs2(1,1);
return mx;
}
#ifdef local
int main(){
freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);
int n,m,l;
cin>>n>>m>>l;
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,l,a,b,t)<<'\n';
}
#else
#endif
Compilation message
/usr/bin/ld: /tmp/cc3tEhML.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
