#include "dreaming.h"
#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[MAXN][2],arr[MAXN],ans,ans1,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;
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[i][0]) mx[i][0]=dpd[g[i][j].ff]+g[i][j].ss;
sort(mx[i],mx[i]+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[i][1]) dpu[g[i][j].ff]=max(dpu[i],mx[i][0])+g[i][j].ss;
else dpu[g[i][j].ff]=max(dpu[i],mx[i][1])+g[i][j].ss;
}
ans1=max(ans1,max(mx[i][0],dpu[i])+mx[i][1]);
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;
// cout<<mx[i][1]+mx[i][0]<<endl;
ind++;
}
// cout<<ans1<<endl;
sort(arr,arr+ind);
ans=max(arr[ind-3]+arr[ind-2]+2*l,arr[ind-1]+arr[ind-2]+l);
return max(ans,ans1);
}
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:16: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:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<g[i].size(); j++){
~^~~~~~~~~~~~
/tmp/ccxBfqKH.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc3SkWzw.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
