#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int B = 1e5 + 100;
const int INF = 1e9 + 10000000;
vector <pair <int,int> > reb[B];
multiset <int> s[B];
vector <int> g;
bool was[B];
int mx1[B];
int mx2[B];
pair <int,int> now = {INF,0};
int pred[B];
int parent(int v) {
return pred[v];
}
int mn[B];
int mxlen;
void precalc(int v,int strt) {
was[v] = true;
pred[v] = strt;
g.push_back(v);
for(auto u:reb[v]) {
if(was[u.f]) continue;
precalc(u.f,strt);
int rast = u.s + mx1[u.f];
if(rast > mx1[v]) {
mx2[v] = mx1[v];
mx1[v] = rast;
}
else if(rast > mx2[v]) {
mx2[v] = rast;
}
}
}
int dp[B];
void dfs(int v) {
now = min(now,{mx1[v],v});
was[v] = true;
vector <pair <int,int> > q;
s[v].insert(0);
for(auto u:reb[v]) {
if(was[u.f]) continue;
s[v].insert(mx1[u.f] + u.s);
q.push_back(u);
}
for(auto u:q) {
if(was[u.f]) continue;
s[v].erase(s[v].find(mx1[u.f] + u.s));
int rast = *--s[v].end() + u.s;
s[u.f].insert(*--s[v].end() + u.s);
s[v].insert(mx1[u.f] + u.s);
if(rast > mx1[u.f]) {
mx2[u.f] = mx1[u.f];
mx1[u.f] = rast;
}
else if(rast > mx2[u.f]) {
mx2[u.f] = rast;
}
dfs(u.f);
}
}
void check(int v) {
precalc(v,v);
for(auto x:g) was[x] = false;
dfs(v);
g.clear();
mn[parent(now.s)] = now.f;
now = {INF,0};
}
multiset <int> nows;
int solve(int v,int L) {
nows.erase(nows.find(mn[parent(v)]));
vector <int> x = {*--nows.end() + L,*----nows.end() + L,mx1[v],mx2[v]};
sort(x.begin(),x.end());
nows.insert(mn[parent(v)]);
return x[3] + x[2];
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int n = N,m = M;
for(int i = 0;i < m;i++) {
reb[A[i] + 1].push_back({B[i] + 1,T[i]});
reb[B[i] + 1].push_back({A[i] + 1,T[i]});
}
for(int i = 1;i <= n;i++) {
if(!was[i]) check(i);
}
nows.insert(-INF);
nows.insert(-INF);
nows.insert(-INF);
nows.insert(-INF);
for(int i = 1;i <= n;i++) {
if(parent(i) == i) {
nows.insert(mn[i]);
}
}
//cout << "Start: ";
//for(auto x:nows) cout << x << " ";
//cout << endl;
for(int i = 1;i <= n;i++) mxlen = max(mxlen,mx1[i]);
int ans = INF;
for(int i = 1;i <= n;i++) {
ans = min(ans,solve(i,L));
}
return max(ans,mxlen);
};
/*
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
cout.tie(0);
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/ccZ51GMY.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
