#include <bits/stdc++.h>
#define s second
#define f first
#define ll long long int
#define pb push_back
using namespace std;
const int N=1e5+7;
vector<pair<int,int> > adj[N];
bool vis[N];
int d[N];
int par[N];
int c[N];
int mx;
int start=-1,tok=-1;
void dfs(int u,int p,int l){
vis[u]=1;
for(auto v:adj[u]) {
if(v.f==p) {
continue;
}
dfs(v.f,u,l+v.s);
}
if(l>mx) {
mx=l;
start=u;
}
}
void dfs2(int u,int p,int l){
vis[u]=1;
for(auto v:adj[u]) {
if(v.f==p) {
continue;
}
par[v.f]=u;
d[v.f]=d[u]+v.s;
dfs2(v.f,u,l+v.s);
}
if(l>mx) {
mx=l;
tok=u;
}
}
int radius(int u,int p){
//memset(par,-1,sizeof par);
mx=0;
start=-1; tok=-1;
dfs(u,p,0);
mx=0;
if(start==-1) {
return 0;
}
dfs2(start,p,0);
int diameter=mx;
int ans=1e9;
for(int u=tok; u!=start; u=par[u]) {
//cout<<u<<" "<<d[u]<<endl;
ans=min(ans,max(diameter-d[u],d[u]));
}
// cout<<ans<<endl;
return ans;
}
int main(){
int n,m,l;
cin>>n>>m>>l;
for(int i=1; i<=m; i++) {
int u,v,w;
cin>>u>>v>>w;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
int cnt=1;
for(int i=0; i<n; i++) {
if(!vis[i]) {
vis[i]=1;
//dfs(i,-1,0);
c[cnt]=radius(i,-1);
cnt++;
}
}
//cout<<radius(4,-1)<<endl;
int mx1=0;
int mx2=0;
for(int i=1; i<cnt; i++) {
if(c[i]>mx1) {
mx2=mx1;
mx1=c[i];
}
else if(c[i]>mx2) {
mx2=c[i];
}
}
int lol=mx1+mx2+l;
cout<<lol<<endl;
return 0;
}
Compilation message
/tmp/ccPswpnz.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccJoHTYr.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccJoHTYr.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
