#include <bits/stdc++.h> using namespace std; #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define _ << " " << #define lf "\n" #define ff endl #ifndef EVAL #define infor(fmt, ...) do { fprintf(stderr, fmt, ##__VA_ARGS__); } while(0) #define infof(fmt, ...) do { fprintf(stderr, fmt"\n", ##__VA_ARGS__); } while(0) #else #define infor(...) #define infof(...) #endif using ll = long long; int tunnel(int N, int M, int L, vector<int> A, vector<int> B, vector<int> C) { vector<vector<array<int, 2>>> adj(N); for(int i = 0; i < M; ++i) { adj[A[i]].push_back({B[i], C[i]}); adj[B[i]].push_back({A[i], C[i]}); } vector<int> d(N); vector<int> st(N); vector<bool> vis(N); auto dfs = [&](int v, auto &&dfs) -> void { st[v] = d[v]; vis[v] = 1; for(auto [u, w]: adj[v]) { if(vis[u]) continue; d[u] = w + d[v]; dfs(u, dfs); st[v] = max(st[v], st[u]); } }; for(int i = 0; i < N; ++i) if(!vis[i]) dfs(i, dfs); fill(all(vis), 0); auto reroot = [&](int v, int up, auto &&reroot) -> int { infof("... reroot(%d, %d)", v, up); vis[v] = 1; vector<array<int, 2>> ups = {{max(up, 0), v}}; for(auto [u, w]: adj[v]) { if(vis[u]) continue; ups.push_back({st[u] - d[u] + w, u}); } infor("ups[%d]:"); for(auto [x, n]: ups) infor(" (%d, %d)", x, n); infof(""); sort(rall(ups)); int mn = max(st[v] - d[v], up); for(auto [u, w]: adj[v]) { if(vis[u]) continue; int up_u = ups[0][1] != u ? ups[0][0] : ups[1][0]; infof("... - calling %d with up_u = %d + w", u, up_u); mn = min(mn, reroot(u, up_u + w, reroot)); } return mn; }; vector<int> c; for(int i = 0; i < N; ++i) { if(!vis[i]) infof("------"); if(!vis[i]) c.push_back(reroot(i, 0, reroot)); } infor("c:"); for(auto x: c) infor(" %d", x); infof(""); sort(rall(c)); int ans = c[0]; if(c.size() > 1) ans = max(ans, c[0] + c[1] + L); if(c.size() > 2) ans = max(ans, c[1] + c[2] + 2 * L); infof("============="); fill(all(vis), 0); auto diam = [&](int v, int f, auto &&diam) -> array<int, 2> { vis[v] = 1; array<int, 2> mx = {0, v}; for(auto [u, w]: adj[v]) { if(u == f) continue; auto sus = diam(u, v, diam); sus[0] += w; mx = max(mx, sus); } return mx; }; for(int i = 0; i < N; ++i) { if(vis[i]) continue; auto [_x, j] = diam(i, -1, diam); auto [x, _j] = diam(j, -1, diam); infof("diam[%d] is %d", i, x); ans = max(ans, x); } return ans; } #ifndef EVAL int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, M, L; cin >> N >> M >> L; vector<int> A(M), B(M), C(M); for (int i = 0; i < M; i ++) cin >> A[i] >> B[i] >> C[i]; cout << tunnel(N, M, L, A, B, C) << '\n'; } #endif

/usr/bin/ld: /tmp/ccPcfcxY.o: in function `main':
grader.c:(.text.startup+0xc5): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status