#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
const ld PI = 3.1415926535;
const int N = 100000+1;
const int M = 7e6 + 1;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
vector<pll> g[N];
ll mxd[N], mxdu[N], used[N];
ll dfs1(int v, int p){
used[v] = 1;
vector<ll> ve = {};
ll cans = 0;
for(auto e : g[v]){
ll u = e.F, w = e.S;
if(u != p){
cans = max(cans, dfs1(u, v));
ve.pb(mxd[u] + w);
}
}
sort(all(ve));
reverse(all(ve));
if(sz(ve) == 0){
mxd[v] = 0;
return cans;
}
mxd[v] = ve[0];
if(sz(ve) == 1){
return max(ve[0], cans);
}
return max(ve[1] + ve[0], cans);
}
ll dfs2(int v, int p){
used[v] = 1;
multiset<ll> ms;
for(auto e : g[v]){
ll u = e.F, w = e.S;
if(u != p){
ms.insert(mxd[u] + w);
}
}
ll mx = infl;
for(auto e : g[v]){
ll u = e.F, w = e.S;
if(u != p){
ms.erase(ms.find(mxd[u] + w));
if(sz(ms) > 0)
mxdu[u] = max(mxdu[v] + w, *ms.rbegin() + w);
else
mxdu[u] = mxdu[v] + w;
ms.insert(mxd[u] + w);
mx = min(mx, dfs2(u, v));
}
}
return min(mx, max(mxd[v], mxdu[v]));
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]){
for(int i = 1; i <= m; i++){
g[a[i - 1]].pb({b[i - 1], t[i - 1]});
g[b[i - 1]].pb({a[i - 1], t[i - 1]});
}
ll ans = 0;
for(int i = 0; i < n; i++){
if(!used[i]){
ans = max(ans, dfs1(i, -1));
}
}
memset(used, 0, sizeof used);
multiset<ll> ms;
vector<ll> rs = {};
ll dada[n];
for(int i = 0; i < n; i++){
if(!used[i]){
dada[i] = dfs2(i, -1);
rs.pb(i);
ms.insert(dada[i]);
}
}
ll ret = infl;
for(auto v : rs){
ms.erase(ms.find(dada[v]));
if(sz(ms) == 0)
return ans;
if(sz(ms) == 1){
ret = min(ret, max(ans, *ms.rbegin() + dada[v] + l));
}else{
auto it = ms.rbegin();
ll a = *it;
it++;
ll b = *it;
ret = min(ret, max(ans, max(*ms.rbegin() + dada[v] + l, a + b + 2 * l)));
}
ms.insert(dada[v]);
}
return ret;
}
/*signed 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) << '\n';
}*/
Compilation message
/usr/bin/ld: /tmp/ccoJCtff.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
