#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>vct[100000];
vector<pair<int,int>>vec[100000];
vector<pair<int,int>>voc[100000];
map<int,int>mp[100000];
int fath[100000];
int val[100000];
int n,m,l,f,ans;
int diam(int in){
deque<pair<int,int>>dq={{in,0}};
map<int,bool>vis;
vis[in]=1;
int x=0,y=0;
while(dq.size()){
int a=dq.front().first,b=dq.front().second;
dq.pop_front();
if(b>=y){
x=a;
y=b;
}
for(auto &i:vct[a]){
if(!vis[i.first]){
vis[i.first]=1;
dq.push_back({i.first,b+i.second});
}
}
}
dq.push_back({x,0});
x=0;y=0;
vis.clear();
vis[dq.back().first]=1;
while(dq.size()){
int a=dq.front().first,b=dq.front().second;
dq.pop_front();
if(b>=y){
x=a;
y=b;
}
for(auto &i:vct[a]){
if(!vis[i.first]){
vis[i.first]=1;
dq.push_back({i.first,b+i.second});
}
}
}
return y;
}
int dfs1(int in){
for(auto &i:vec[in]){
int g=dfs1(i.first)+i.second;
val[in]=max(val[in],g);
voc[in].push_back({g,i.first});
}
sort(voc[in].begin(),voc[in].end());
return val[in];
}
void dfs2(int in,int x){
if(fath[in]!=-1){
int k=voc[fath[in]].size()-1;
if(voc[fath[in]][k].second==in)k--;
x=max(x,voc[fath[in]][k].first+mp[fath[in]][in]);
}
f=min(f,max(x,val[in]));
for(auto &i:vec[in])dfs2(i.first,x+i.second);
}
int travelTime(int N, int M, int L, int a[], int b[], int t[]){
n=N,m=M,l=L;
for(int i=0;i<n;i++)voc[i].push_back({0,-1});
for(int i=0;i<n;i++)fath[i]=-1;
for(int i=0;i<m;i++){
vct[a[i]].push_back({b[i],t[i]});
vct[b[i]].push_back({a[i],t[i]});
}
vector<int>vis(n);
deque<int>v;
for(int i=0;i<n;i++){
if(vis[i])continue;
vis[i]=1;
vector<int>vc={i};
{
deque<int>dq={i};
while(dq.size()){
int a=dq.front();
dq.pop_front();
for(auto &w:vct[a]){
if(!vis[w.first]){
vis[w.first]=1;
vec[a].push_back(w);
fath[w.first]=a;
mp[a][w.first]=w.second;
dq.push_back(w.first);
vc.push_back(w.first);
}
}
}
}
f=INT_MAX;
ans=max(ans,diam(i));
if(vc.size()==1)f=0;
else{
dfs1(i);
dfs2(i,0);
}
v.push_back(f);
}
sort(v.begin(),v.end());
while(v.size()>1){
ans=max(ans,v.back()+v[0]+l);
v.back()=max(v.back(),v[0]+l);
v.pop_front();
}
return ans;
}
int main(){
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);
}
Compilation message
/usr/bin/ld: /tmp/ccGdQFRk.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3BJKii.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
