#include "dreaming.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 100'000;
vector<pii> adj[MAXN + 10];
int h1[MAXN + 10];
int h2[MAXN + 10];
inline void link(int a, int b, int c) {
adj[a].eb(b, c);
adj[b].eb(a, c);
}
void dfs1(int n, int p) {
h1[n] = 0;
for(auto &e:adj[n]) if(e.F != p) {
dfs1(e.F, n);
int h = h1[e.F] + e.S;
if(h > h1[n]) {
h2[n] = h1[n];
h1[n] = h;
} else if(h > h2[n]) {
h2[n] = h;
}
}
}
int mnh, mni;
void dfs2(int n, int p, int h3) {
int h = max(h3, h1[n]);
if(h < mnh) {
mnh = h;
mni = n;
}
for(auto &e:adj[n]) if(e.F != p) {
int h4 = h1[n];
if(h4 == h1[e.F] + e.S) h4 = h2[n];
h4 = max(h4, h3) + e.S;
dfs2(e.F, n, h4);
}
}
// {depth, index}
pii dfs3(int n, int p) {
pii res(0, n);
for(auto &e:adj[n]) if(e.F != p) {
pii r2 = dfs3(e.F, n);
r2.F += e.S;
res = max(res, r2);
}
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
For(i, 0, M - 1) {
link(A[i], B[i], T[i]);
}
memset(h1, -1, sizeof(h1));
vector<pii> rt; // {height, index}
For(i, 0, N - 1) if(h1[i] == -1) {
dfs1(i, i);
mnh = 2e9; mni = -1;
dfs2(i, i, 0);
rt.eb(mnh, mni);
}
sort(all(rt));
For(i, 0, sz(rt) - 2) {
link(rt.back().S, rt[i].S, L);
}
return dfs3(dfs3(0, 0).S, -1).F;
}
#ifdef NYAOWO
const int _MAXN = 100'000;
int _A[_MAXN + 10];
int _B[_MAXN + 10];
int _T[_MAXN + 10];
int32_t main() {
int n, m, l; cin >> n >> m >> l;
For(i, 0, m - 1) {
cin >> _A[i];
cin >> _B[i];
cin >> _T[i];
}
int ret = travelTime(n, m, l, _A, _B, _T);
cout << ret << "\n";
return 0;
}
#endif
Compilation message
/usr/bin/ld: /tmp/ccNP7sUI.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
