#include "dreaming.h" #include <bits/stdc++.h> using namespace std; const int INF = 1e9; const int MAXN = 1e5; vector<vector<pair<int, int>>> adj(MAXN); vector<bool> vis(MAXN, false); vector<int> dist(MAXN, 0); int curmn = -1, curmx = -1; // {radius, diameter} void dfs(int u, int par) { vis[u] = true; dist[u] = 0; for (auto [v, d] : adj[u]) { if (v == par) continue; if (!vis[v]) { dfs(v, u); dist[u] = max(dist[u], dist[v] + d); } } } void reroot(int u, int par) { int mx1 = 0, mx2 = 0; for (auto &[v, d] : adj[u]) { if (v == par) continue; int val = dist[v] + d; if (val > mx1) { mx2 = mx1; mx1 = val; } else if (val > mx2) mx2 = val; } int old = dist[u]; dist[u] = mx1; curmn = min(curmn, dist[u]); curmx = max(curmx, mx1 + mx2); for (auto &[v, d] : adj[u]) { if (v == par) continue; int saved = dist[u]; if (dist[v] + d == mx1) dist[u] = mx2; reroot(v, u); dist[u] = saved; } dist[u] = old; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for (int i = 0; i < M; ++i) { int u = A[i], v = B[i], d = T[i]; adj[u].push_back({v, d}); adj[v].push_back({u, d}); } vector<int> a; int globalDia = 0; for (int i = 0; i < N; ++i) { if (vis[i]) continue; dfs(i, -1); curmn = INF; curmx = 0; reroot(i, -1); a.push_back(curmn); globalDia = max(globalDia, curmx); } sort(a.rbegin(), a.rend()); int ans = 0; if (a.size() >= 2) ans = max(ans, a[0] + L + a[1]); if (a.size() >= 3) ans = max(ans, a[1] + 2 * L + a[2]); return max(ans, globalDia); }