#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ar array
#define db double
#define sz(x) (int)x.size()
const db pi = acos(-1);
const int mxn = 1e5 + 7;
int in[mxn], out[mxn];
int vis[mxn];
vector<ar<int, 2> > g[mxn];
int tmp, node;
int d(int u)
{
return in[u] + out[u];
}
int leaf(int u)
{
return max(in[u], out[u]);
}
void dfs(int u)
{
vis[u] = 1;
for (auto [v, w] : g[u])
{
if (vis[v]) continue;
dfs(v);
in[u] = max(in[u], in[v] + w);
}
}
void dfs2(int u, int p)
{
int mx1 = 0, mx2 = 0;
for (auto [v, w] : g[u])
{
if (v == p) continue;
if (in[v] + w > mx1) mx2 = mx1, mx1 = in[v] + w;
else mx2 = max(mx2, in[v] + w);
}
for (auto [v, w] : g[u])
{
if (v == p) continue;
if (in[v] + w == mx1) out[v] = max(out[u], mx2) + w;
else out[v] = max(out[u], mx1) + w;
dfs2(v, u);
}
if (tmp > leaf(u))
{
tmp = leaf(u);
node = u;
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (int i = 0; i < M; i++)
{
g[A[i] + 1].push_back({B[i] + 1, T[i]});
g[A[i] + 1].push_back({A[i] + 1, T[i]});
}
vector<int> ans;
for (int i = 1; i <= N; i++)
if (!vis[i])
{
tmp = mxn;
dfs(i);
dfs2(i, i);
ans.push_back(node);
// cout << i - 1 << ' ' << tmp << '\n';
}
if (M == N - 1) return d(ans[0]);
sort(ans.begin(), ans.end(), [](int u, int v)
{
return leaf(u) < leaf(v);
});
int mx = d(ans[0]);
// cout << mx << '\n';
tmp = leaf(ans[0]);
for (int i = 1; i < sz(ans); i++)
{
mx = max(mx, d(ans[i]));
mx = max(mx, tmp + L + leaf(ans[i]));
tmp = min(max(tmp + L, leaf(ans[i])), max(leaf(ans[i]) + L, tmp));
// cout << mx << '\n';
}
return mx;
};
// int n, m, l;
// int a[mxn], b[mxn], t[mxn];
// signed main()
// {
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// // De nghi ko bat ultra instinct tay nhanh hon nao luc lam bai
// 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);
// /*
// 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*/
// return 0;
// }
Compilation message
/usr/bin/ld: /tmp/ccr2SI0K.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
