#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define MAXN 100005
#define INF 999999999
using namespace std;
int ind,dpu[MAXN],dpd[MAXN],mx[2],arr[MAXN],ans,per[MAXN];
int N,M,L,A[MAXN],B[MAXN],T[MAXN];
vector <pair<int,int> > g[MAXN];
bool fl[MAXN];
void dfs1(int i){
fl[i]=1;
for (int j=0; j<g[i].size(); j++){
if (fl[g[i][j].ff]) continue;
dfs1(g[i][j].ff);
dpd[i]=max(dpd[i],dpd[g[i][j].ff]+g[i][j].ss);
}
fl[i]=0;
}
void dfs2(int i){
fl[i]=1;
mx[0]=mx[1]=0;
arr[ind]=min(arr[ind],max(dpu[i],dpd[i]));
// cout<<i<<" - "<<dpu[i]<<" "<<dpd[i]<<endl;
for (int j=0; j<g[i].size(); j++){
if (fl[g[i][j].ff]) continue;
if (dpd[g[i][j].ff]+g[i][j].ss>mx[0]) mx[0]=dpd[g[i][j].ff]+g[i][j].ss;
sort(mx,mx+2);
}
// cout<<mx[0]<<" - "<<mx[1]<<endl;
for (int j=0; j<g[i].size(); j++){
if (fl[g[i][j].ff]) continue;
if (dpd[g[i][j].ff]+g[i][j].ss==mx[1]) dpu[g[i][j].ff]=max(dpu[i],mx[0])+g[i][j].ss;
else dpu[g[i][j].ff]=max(dpu[i],mx[1])+g[i][j].ss;
}
for (int j=0; j<g[i].size(); j++){
if (fl[g[i][j].ff]) continue;
dfs2(g[i][j].ff);
}
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
for (int i=0; i<m; i++){
g[a[i]].pb({b[i],t[i]});
g[b[i]].pb({a[i],t[i]});
}
for(int i=0; i<n; i++){
if (fl[i]) continue;
arr[ind]=INF;
dfs1(i);
dfs2(i);
// cout<<"------------ arr - "<<arr[ind]<<" "<<i<<endl;
ind++;
}
sort(arr,arr+ind);
for (int i=0; i<ind/2; i++){
per[ind-1-i]=arr[i*2+1];
per[i]=arr[i*2];
}
for (int ln=1; ln<ind; ln++){
for (int j=0; j<ind-ln; j++)
ans=max(ans,l*ln+per[j]+per[j+ln]);
}
return ans;
}
// int main() {
// 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;
// }
/*
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: In function 'void dfs1(int)':
dreaming.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<g[i].size(); j++){
~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int)':
dreaming.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<g[i].size(); j++){
~^~~~~~~~~~~~
dreaming.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<g[i].size(); j++){
~^~~~~~~~~~~~
dreaming.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<g[i].size(); j++){
~^~~~~~~~~~~~
/tmp/ccoAGJAW.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
